分支定界法与分支定价法
#! https://zhuanlan.zhihu.com/p/598134928 # 分支定界法与分支定价法
分支定界法（Branch and bound）
分支定界法一般用于解决整数线性规划和混合整数线性规划。它本质上是一种基于搜索的算法，是比较暴力的，并且在极坏情况下可能会退化成枚举。
对于如下混合整数线性规划问题
\[ \min_{x,y} f(x,y) \\ {s.t.}\left \{ \begin{array}{l} Ax = 0,By=0\\ x\in R^{n_1},y\in Z^{n_2} \end{array} \right. \]
其中x是普通变量，y是整数变量。我们把y是整数这个约束松弛掉，就得到松弛后问题
\[ \min_{x,y} f(x,y) \\ {s.t.}\left \{ \begin{array}{l} Ax = 0,By=0\\ x\in R^{n_1},y\in R^{n_2} \end{array} \right. \]
注意，这是一个普通的线性规划问题，我们可以使用单纯形法或者其它线性规划算法解决。但求出来的解\(y^*\)中很有可能有一些不是整数，导致解不在原问题的可行域中。显然，这个松弛问题的解是原问题的一个下界。接下来开始进行分支限界，取\(y^*\)中一个不是整数的分量\(y_j^*\)，构造这样两个分支问题
第一个分支问题 \[ \min_{x,y} f(x,y) \\ {s.t.}\left \{ \begin{array}{l} Ax = 0,By=0\\ y_j \ge \lceil y_j^* \rceil \\ x\in R^{n_1},y\in R^{n_2} \end{array} \right. \]
第二个分支问题 \[ \min_{x,y} f(x,y) \\ {s.t.}\left \{ \begin{array}{l} Ax = 0,By=0\\ y_j \le \lfloor y_j^* \rfloor \\ x\in R^{n_1},y\in R^{n_2} \end{array} \right. \]
这样我们就有了两个新的节点，接下来只要递归的对这两个节点继续分支限界就可以了，直到获得整数解或无解就停止。如图
这样就构成了一颗搜索树。注意这棵树有这样几个特点
- 由于分支限界是不断进行的，我们一直在添加约束，所以目标函数值一定是在不断增大的，后面的节点目标函数值一定大于前面节点（父节点，祖先节点）的目标函数值
- 构成方式是不唯一的，因为每次求解得到的\(y^*\)中非整数变量可能不止一个，可以选取其中任意一个进行分支限界
- 搜索方式是不唯一的，可以使用深度优先搜索（DFS），广度优先搜索（BFS）等多种方式搜索
在搜索的过程中，还需要注意进行剪枝。无论搜索的顺序如何，一旦获得一个可行解，那么它会是解的上界，我们记忆下这个上界。在接下来的搜索过程中，一旦当前的目标函数值超过了上界，就剪掉这棵子树。
分支定价法（Branch and price）
分支定价法其实就是分支定界法+列生成算法。列生成算法的具体描述可以看本专栏之前的文章。
分支定界法中，求解每个节点对应的松弛问题的时候，是直接求解的。而分支定价法中使用列生成算法来求解。其好处是显然的，列生成算法在变量很多的情况比普通的单纯形法有更好的性能。而且，在解决某个节点的RMP的时候，可以不用重新构建问题，运行一次完整的列生成算法，而是继承父节点的RMP问题，并添加约束，这可能会进一步的加速求解过程。