分支定界法详解

1.1、概念：分支定界算法（Branchandbound,简称为 BB、B&B,orBnB）始终围绕着一颗搜索树进行的，我们将原问题看作搜索树的根节点，从这里出发，分支的含义就是将大的问题分割成小的问题。大问题可以看成是搜索树的父节点，那么从大问题分割出来的小问题就是父节点的子节点了。分支的过程就是不断给树增加子节点的过程。而定界就是在分支的过程中检查子问题的上下界，如果子问题不能产生一比当前最优解还要优的解，那么砍掉这一支。直到所有子问题都不能产生一个更优的解时，算法结束。2、例子：用 BB 算法求解下面的整数规划模型MaximizeSubjectto5xi+8x2+6x35因为求解的是最大化问题，我们不妨设当前的最优解 BestV 为-INF,表示负无穷。Ma4 心+9 心+6 心2.3.首先从主问题分出两支子问题：4X1+9X2+6[+8X2<6xlrr2arebinaryvariables通过线性松弛求得两个子问题的 upperbound 为 Z_LP1=12.75，Z_LP2=12.2。由于 Z_LP1 和 Z_LP2 都大于 BestV=-INF,说明这两支有搞头，继续往下。4.从节点 1 和节点 2 两个子问题再次分支，得到如下结果：0x3x3=[ZLP=1275・infeasibleZ=10,integeroptii子问题 3 已经不可行，无需再理。子问题 4 通过线性松弛得到最优解为 10，刚好也符合原问题 0 的所有约束，在该支找到一个可行解，更新 BestV=10。子问题 5 通过线性松弛得到 upperbound 为 11.87＞当前的 BestV=10，因此子问题 5 还有戏，待下一次分支。而子问题 6 得到 upperbound 为 9＜当前的 BestV=10，那么从该支下去找到的解也不会变得更好，所以剪掉！Z=10?integerX1yoptimalinfeasible6.5.对节点 5 进行分支，得到：infeasible子问题 7 不可行，无需再理。子问题 8 得到一个满足原问题 0 所有约束的解，但是目标值为 4＜当前的 BestV=10,所以不更新 BestV,同时该支下去也不能得到更好的解了。ZLP=12.757.此时，所有的分支遍历都完成，我们最终找到了最优解。Optimalsolutionisfound:Zg=103、算法过程(以最小化问题 minimizef(x)为例)1、使用启发式，找到优化问题的解决方案 xh。存储其值，B=F(x_h)。(如果没有启发式可用，则将 B 设置为无穷大。)B 将表示到目前为止找到的最佳解，并将用作候选解的上界。2、初始化队列以保存部分解决方案，但不分配任何问题变量。3、循环直到队列为空：3.1 从队列中取出一个节点 N.3.2 如果 N 代表单个候选解 x 和((x)