下载文档原格式
数模常⽤算法系列--整数线性规划（分枝定界法）、整数⾮线性规划（蒙特卡洛法）整数线性规划求解----分枝定界法什么是整数规划?线性规划中的变量（部分或全部）限制为整数时，称为整数规划。
若在线性规划模型中,变量限制为整数，则称为整数线性规划。
⽬前所流⾏的求解整数规划的⽅法，往往只适⽤于整数线性规划。
⽬前还没有⼀种⽅法能有效地求解⼀切整数规划。
整数规划的分类- 变量全限制为整数时，称(完全)整数规划- 变量部分限制为整数时，称混合整数规划什么是分枝定界法原理如下：设有最⼤化的整数规划问题A,与它相应的线性规划为问题B,从解问题B开始,若其最优解不符合A的整数条件,那么B的最优⽬标函数必是A的最优⽬标函数z^*的上界\overline{z}；⽽A的任意可⾏解的⽬标函数值将是z^*的⼀个下界\underline z ,分枝定界法就是将B的可⾏域分成⼦区域的⽅法。
逐步减⼩\overline z和增⼤\underline z最终求到z^*本质就是个分治回溯,逼近最⼤值的算法。
Matlab算法如下：（强烈警告，（不会验证）由于⽐较懒，并未对算法正确性验证，思路上验证了⼀下没问题就码上来了，如果有错，请⼀定联系~~）% c,A,Aeq,Beq,LB,UB,是linprog函数的相关参数，知道了它们就可以求出对应的线性规划最优解，% now是⽬前已经知道的整数解的最⼤值function y = control(c,A,Aeq,Beq,LB,UB,now)ret = 0;[x,fval] = linprog(c,A,Aeq,Beq,LB,UB); % x是最优解的解向量，fval是对应的函数值if fval < nowy = fval;return;end % 如果得到的当前最优解fval⼩于已知的now,那说明最优整数解不在这个区间，则剪枝返回。
for i = 1 : length(x)if rem(x(i),1) ~= 0 % rem(x,1)如果返回值不为0,则表⽰是⼩数。
第 5 章分枝定界任何美好的事情都有结束的时候。
现在我们学习的是本书的最后一章。
幸运的是，本章用到的大部分概念在前面各章中已作了介绍。
类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间（常用的树结构是第1 6章所介绍的子集树和排列树）。
然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。
本章与第1 6章所考察的应用完全相同，因此，可以很容易比较回溯法与分枝定界法的异同。
相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。
5.1 算法思想分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。
每个活节点有且仅有一次机会变成E-节点。
当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。
在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。
从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。
有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：1) 先进先出（F I F O）即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。
2) 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。
如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是具有最大收益的活节点。
例5-1 [迷宫老鼠] 考察图16-3a 给出的迷宫老鼠例子和图1 6 - 1的解空间结构。
使用F I F O 分枝定界，初始时取（1，1）作为E-节点且活动队列为空。
迷宫的位置（ 1 , 1）被置为1，以免再次返回到这个位置。
分支定界法分支定界法，顾名思义，就是按照定好的界进行分支。
这里说的分支意思是“剪枝”。
剪的枝是问题解空间树的枝。
所谓解空间树，即此问题所有解和中间解形成的树型结构，是有序的。
常有排列树和子集树之分，举个例子，n个物品的0-1背包问题的解空间树就是子集树(每个物品都可能为0或1)，而最短路径问题的解空间树是一颗排列树。
分支定界法一般有两种实现形式：1.优先队列法2.FIFO队列法。
这与分支定界的思想无太多本质联系，只是前者在一般情况下能更快的求得问题解。
分支定界法要对问题的解空间树进行“剪枝”操作以减少对解空间树的搜索。
那么问题是，如何“剪枝”？这就要回答如何定界的问题。
在分支定界法中，“界”的作用就是用来阻止对不可行分支的搜索的。
当解空间树很深时（叶子节点为解），如果能在前面几层就预先的知道了“此路不通”或者“此路不是最优”而停止此路的继续，这样能大幅度的提高算法效率。
如何定界要放入具体问题中考虑，一般可以以“理论最大最小”这个概念来求界。
以0-1背包问题为例，设所有物品预先已经按照单位价值量递减排列。
在解空间树的第i层（此时正在考虑第i个物品是否应该被放入的时刻），设左子树为放入i物品，右子树为不放i物品。
那么在确定左子树的上界的时候有：界=当前价值+i的价值+MaxValue(背包剩余重量-i物品重量);其中的MaxValue为放i后剩余背包容量能获得的最大价值，应该注意的是此最大价值为理论意义上的最大价值，比如在继续放入p个后(按单位价值量递减),放不下第p+1个，此时应该按(Value[p+1]/Weight[p+1])*(WeightLeft)来计p+1物品的价值,(实际中不可能放入零点几个某物品。
)；右子树的情形类似。
知道了如何定界，那么在实际流程中就要根据当前目标节点的界来剪枝了（是用上界还是下界，具体问题具体分析）。
今天准备举个稍微有点挑战的例子---NPC问题中的TSP问题。
在TSP问题中，由于是环路，每个节点都要进出各一次，我们可以将每个节点最小的入度和最小的出度的和累加作为一个下界，这个下界几乎不可能达到！（全部最小出度的和即为下面提到的rcost的初值）初始时我们创建一个最小堆，表示活节点队列。
分支定界法基本思路分支定界法（BranchandBound）是一种求解多维空间内最优解的技术，它能够有效地解决数学优化问题，并且在面临一定限制条件的情况下，能够获得较为有效的最优解。
本文将着重介绍分支定界法的基本思路和实施步骤。
1、义问题分支定界法是一种求解多维空间内最优解的技术，它的典型应用有组合优化、资源分配、路径规划等。
组合优化指的是要求设计者给出一系列解决方案，并且找出能够达到目标要求的解决方案，例如求解一个给定的多项式的顶点值问题；资源分配指的是在给定资源限制的情况下，以极小的成本耗费获得最大的收益；路径规划指的是在给定的网络中求一条最优路径，并且求解这条路径的最短路径等。
2、问题抽象分支定界法的基本思路是将复杂的优化问题分解成若干个子问题，逐步进行求解，利用“分支定界”技术来求得该子问题的最小值，然后在各个子问题最小值之间进行比较，得到总体问题的最小值。
在实际应用中，具体步骤是：首先，将原问题抽象为一个数学模型，并将该模型简化为一个多维空间内的数学问题；然后，利用“分支定界”的技术，对其中的多个点进行分枝，即找出最小的点；最后，将该点经过完善的求解后，把它作为最优点，以此作为定界，停止分枝，这个过程重复直至找出全局最优解。
3、实施步骤（1）构造初始子集：构造初始子集是分支定界法的第一步，在构造初始子集时，需要考虑当前子集中变量数量、变量取值范围等因素，构造出一个尽可能大的初始子集。
（2）根据初始子集构造子集树：构造子集树是分支定界法的第二步，根据初始子集构造出一棵完整的子集树，其目的是将多个子集之间的联系关系清楚地表达出来，并且指向每一个子集，使空间复杂度降低。
（3）进行分支：进行分支是分支定界法的第三步，当构造出子集树之后，根据拓扑结构选择一个子集，并将该子集构造成两个新子集，根据确定的拓扑结构继续进行分支并将其更新。
（4）定界：定界是分支定界法的第四步，在分支的时候可以找到一些子集的最小值，其目的是通过对子集最小值的比较，来比较各个子集的最小值，从而可以确定一个全局最小值。
以下内容基本为转载内容:1. 模型整数规划的模型与线性规划基本相同，只是额外的添加了部分变量为整数的约束。
2. 求解步骤整数规划求解的基本框架是分支定界法（Branch and bound，BnB）。
首先去除整数约束得到“松弛模型”，使用线性规划的方法求解。
若有某个变量不是整数，在松弛模型上分别添加约束：x<=floor(A)和x>=ceil(A)然后再分别求解，这个过程叫做分支。
当节点求解结果中所有变量都是整数时，停止分支。
这样不断迭代，形成了一棵树。
定界，指的是叶子节点产生后，相当于给问题定了一个下界。
之后在求解过程中一旦某个节点的目标函数值小于这个下界，那就直接pass，不用再进行分支了；每次新产生叶子节点，则更新下界。
3. python算法实现import mathfrom scipy.optimize import linprogimport sysdef integerPro(c,A,b,Aeq,beq,t=1.0E-12):res=linprog(c,A_ub=A,b_ub=b,A_eq=Aeq,b_eq=beq)if(type(res.x)is float):#produces error codebestX=[sys.maxsize]*len(c)else:bestX=res.xbestVal=sum([x*y for x,y in zip(c,bestX)])if all(((x-math.floor(x))<t or(math.ceil(x)-x)<t)for x in bestX): return(bestVal,bestX)else:ind=[i for i,x in enumerate(bestX)if(x-math.floor(x))>t and (math.ceil(x)-x)>t][0]newCon1=[0]*len(A[0])newCon2=[0]*len(A[0])newCon1[ind]=-1newCon2[ind]=1newA1=A.copy()newA2=A.copy()newA1.append(newCon1)newA2.append(newCon2)newB1=b.copy()newB2=b.copy()newB1.append(-math.ceil(bestX[ind]))newB2.append(math.floor(bestX[ind]))r1=integerPro(c,newA1,newB1,Aeq,beq)r2=integerPro(c,newA2,newB2,Aeq,beq)if r1[0]<r2[0]:return r1else:return r2例子：输入c=[3,4,1]A=[[-1,-6,-2],[-2,0,0]]b=[-5,-3]Aeq=[[0,0,0]]beq= [0]print(integerPro(c,A,b,Aeq,beq))输出(8.0,array([2.,0., 2.]))其中8是目标函数值，2，0，2是3个整数变量的值。
分支定界法基本思路
分支定界法是一种常用的计算机科学解析技术，它的基本思路是
先将复杂的问题分解成简单的子问题，然后将原问题的解决方案由子
问题的解决方案派生出来。
例如，假设某计算机程序需要解决以下问题：找出从一组由零个或多个整数组成的子集的和的最大值。
使用分支定界法来解决这个问题，首先需要将问题分解成子问题，即从一组由一个整数组成的子集中求和的最大值问题，以此类推，一
直到从一组由n个整数组成的子集中求和的最大值。
之后，就可以使用分支定界法正式开始求解。
首先建立一张表，
表中列出了可能的各种子集，但是首先最大值可能是每元素中的一个，之后可以把它们合并到一起，并计算他们的和以及比较哪个更大。
在
把这种可能的每一种结果一一列出来以后，就可以找出最大值，从而
得出原问题的解决方案。
总之，分支定界法是一种通过分解复杂问题，然后从每个子问题
中获得解决方案，最后合并它们来获得原问题的解决方案的技术。
然而，一般来说，这种方法只适用于问题的解决范围有限的情况，当问
题的解决范围变得太大时，该方法就不能采用，因为计算时间特别长。
分支定界法求解整数规划时，如果可行域是有界的,首先容易想到的方法就是穷举变量的所有可行的整数组合，对于变量数较小的情况，这种方法是可行的，也是有效的。
对于大型问题,可行的整数组合数是很大的，穷举法是不可取的。
我们一般仅检查可行的整数组合的一部分,就能定出最优的整数解。
分支定界法(branch and bound method)就是其中一种。
分支定界法可用于解纯整数或混合的整数规划问题。
在20世纪60年代由Land Dakin和Dakin等人提出。
由于这方法灵活且便于计算机求解，所以现在它已是解整数规划的重要方法。
设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B 开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数*z的上界,记作z;而A的任意可行解的目标函数值将是*z的一个下界Z。
分枝定界法就是将B的可行域分成子区域(称为分支)的方法，逐步减小z和增大Z, 最终求到*z。
下面以实例来说明算法的步骤：例1 求解下面整数规划解：先不考虑条件⑸，求解相应的线性规划问题L，得最优解x=4.81，2x=1.82，0z=356（见图）1x=4.81，对问题L分别增加约束条件：该解不是整数解。
选择其中一个非整数变量，如1≤4，≥5 将问题L分解为两个子问题，（分枝），也就是去掉问题L不含整数解的一部分可行域，将原可行域D变为、两部分（如图）因为没有得到整数解，所以继续对L1进行分解，增加约束：≤2，≥3 将分解成问题与，并求得最优解如下：问题的解已是整数解，它的目标值=340，大于问题L4的目标值，所以问题已无必要再分枝。
但由于问题的目标值大于，分解还有可能产生更好的整数解，因此继续对分枝。
增加约束≤1，≥2 将分解成问题与，并求解，结果如下：问题的，所以不必分解了；问题无可行解，于是可以断定问题的解：=4.00，=2.00即为最优整数解。
整个分枝定界过程如下图所示：用分枝定界法求解整数规划的步骤可总结如下：步骤1：求解与整数规划相对应的线性规划L，若L无可行解，则整数规划也没有可行解，计算停；若L 的最优解是整数解，则该解即为整数规划的最优解，计算停；若L的最优解不是整数解，则转步骤2。
