分支定界算法

x_3=1

x_14=0

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\

6

17

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\tilde{x} ^{(5)}\

x_3=0

3

0

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\tilde{x} ^{(3)}\

否

1

4

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\tilde{x} ^{(1)}\



通过定界终止

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\tilde{x} ^{(6)}\

最佳解 以及对应的目标值

15

分支定界提前停止：作为一种启发式算法

分支定界算法（branch and bound algorithm）把部分或枚举策略子集与松弛模型结合起来。其系统地将解进行了分类，并且通过分析相关的松弛模型可以考察分类中是否会存在最优解。更多更细的枚举只会在松弛模型无法确定时产生

9

=1

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\tilde{x} ^{(2)}\

5

8

10

x_2=1

12

最优优先(best first)搜索在每一个循环的阶段，选择具有最优母节点界限的活跃部分解。

深度向前最优回溯(depth forward best back)搜索在一个节点分支后选择最深的活跃部分解，但在终止了一个节点后选择具有最优母节点界限的活跃部分解。

=0

x_12=1

定义 12.49  一个给定混合整数线性规划的整数可行解的凸包(convex hull)，是所有包含每一个这样解的凸集的交集，通俗来讲就是最小的包含这些解的凸集。原理 12.51  如果一个整数规划或混合整数规划具有有限最优解，那么其中一个就是其整数可行解的凸包的极值点。

通过定界终止部分解 的最优可行的完全形式不能使最佳解更优，终止

高莫利割平面（纯整数模型）R.E.Gomory高莫利小数割平面方程（gomory fractional cut）

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\tilde{x} ^{(4)}\

利用母节点界限终止原理 12.35 当一个分支定界搜索找出了一个新的最佳解的时候，对于任何一个还没有被终止的部分解，如果其母节点界限没有比新最佳解的值更优，那么这个部分解就可以被马上终止。如节点12

2

河流能源公司模型min    7 + 12 + 5 + 14                               （总成本）s.t.      300 + 600 + 500 + 1600   700    （需求）            span class=\"equation-text\" contenteditable=\"false\" data-index=\"9\" data-equation=\

x_5=0

18

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\tilde{x} ^{(8)}\

是

16

7

x_10=1

x_7=0

                                                                     NASA资本预算案例选择任务模型max     s.t.                                                                                                                                                                  span class=\"equation-text\" contenteditable=\"false\" data-index=\"14\" data-equation=\"x_{j}\

松弛：定义12.4：如果（P）的每一个可行解都是（P`）的可行解，并且两个模型具有相同的目标函数，则我们称模型（P`）是模型(P)的约束条件松弛（constraint relaxation）

x_7=1

不可行

通过求解终止线性规划松弛模型的最优解满足模型中的所有约束，这个最优解就是  的最优可行的完全模式。这个最佳解就是新的最佳解

 = 1

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\tilde{x} ^{(0)}\

x_14=1

深度优先搜索（depth first）在每个循环处选择一个具有最多部分固定的活跃部分解(例如，搜索树中最深的节点)。

x_4=0

x_10=0

span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\tilde{x} ^{(7)}\

返回

x_2=0

x_9=0

最佳解整数化原理12.33 span style=\"font-size: inherit;\

通过不可行终止若线性规划松弛模型被证明不可行（违反约束），部分解没有任何可行的完全形式，则终止

                                   求初始解1.让唯一的活跃部分解的变量均自由2.初始化解索引  t->03.若模型的任一可行解已知，选择最优的作为最佳解span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"\\hat{x}\

分支原则：原理 12.31：基于线性规划的分支定界算法总是通过对候选问题的松弛模型中非整数的分量施加一个整数约束来完成分支。原理 12.32： 当松弛最优解中有不止一个整数变量取值为分数的时候，基于线性规划的分支定界算法通常通过固定一个最接近整数值的分量来进行分支

t  = t +1

x_12=0

有有效不等式

分支切割算法：

候选问题（candidate problem）定义12..26   在一个优化模型中，与任一部分解相关的候选问题，是部分解中某些变量固定时对应的受限模型。部分解 =(#，1，#，0)来描述。相应的候选问题为:min   s.t.       >=  700         span class=\"equation-text\" contenteditable=\"false\" data-index=\"3\" data-equation=\

x_4=1

 = 0

11

无有效不等式

在节点15求解之后通过母节点界限终止

x_9=1

如何找有用的有效不等式？

 ：表示松弛解：表示松弛解目标值

                             松弛1.选择1个存在的部分解 2.尝试求解1个与 对应的候选问题的线性规划松弛模型

14

基于线性规划的分支定界法（对于0-1整数规划）

定义12.41  如果一个线性不等式对于一个离散优化模型的所有(整数)可行解都成立，那么这个线性不等式就是这个给定离散优化模型的有效不等式。原理 12.42 为了加强一个松弛模型的有效性，一个有效不等式必须切割(使不可行)一些在现在松弛模型中可行，但在完全整数规划模型中并不可行的解。此时该有效不等式对可以增强松弛问题的有效性，称之为 有用的有效不等式分支切割算法在枚举过程进行下去的时候，动态整合了有效不等式和分支定界搜索定义 12.43 分支切割算法通过在分支一个部分解之前，尝试用新的有效不等式来加强松弛模型的有效性，进而加强了分支定界算法 所代表的基础分支定界策略。新增的约束应该切割掉(使不可行)最新得出的松弛模型的最优解。

x_5=1

13

停止活跃的部分解是否存在

线性规划松弛/连续松弛定义12.6：连续松弛是一种约束条件的松弛：保留所有其他约束，但将任何离散变量看成连续变量

 有效不等式（切割平面）试着找出1个完全整数规划模型的有效不等式，使得当前的松弛最优解不满足这个不等式。如果成功找到这样的不等式，将其作为一个新约束添加至完整模型，设置t=t+1

更新最佳解

19