分支定界法与分支定价法

#! https://zhuanlan.zhihu.com/p/598134928 # 分支定界法与分支定价法

分支定界法（Branch and bound）

分支定界法一般用于解决整数线性规划和混合整数线性规划。它本质上是一种基于搜索的算法，是比较暴力的，并且在极坏情况下可能会退化成枚举。

对于如下混合整数线性规划问题

$$\begin{gathered} \underset{x,y}{min}f(x,y) \\ s.t.\{\begin{array}{l}Ax=0,By=0\\ x\in R^{n_1},y\in Z^{n_2}\end{array} \end{gathered}$$

其中x是普通变量，y是整数变量。我们把y是整数这个约束松弛掉，就得到松弛后问题

$$\begin{gathered} \underset{x,y}{min}f(x,y) \\ s.t.\{\begin{array}{l}Ax=0,By=0\\ x\in R^{n_1},y\in R^{n_2}\end{array} \end{gathered}$$

注意，这是一个普通的线性规划问题，我们可以使用单纯形法或者其它线性规划算法解决。但求出来的解$y^{\ast }$中很有可能有一些不是整数，导致解不在原问题的可行域中。显然，这个松弛问题的解是原问题的一个下界。接下来开始进行分支限界，取$y^{\ast }$中一个不是整数的分量$y_j^{\ast }$，构造这样两个分支问题

第一个分支问题 $$\begin{gathered} \underset{x,y}{min}f(x,y) \\ s.t.\{\begin{array}{l}Ax=0,By=0\\ y_j\ge \lceil y_j^{\ast }\rceil \\ x\in R^{n_1},y\in R^{n_2}\end{array} \end{gathered}$$

第二个分支问题 $$\begin{gathered} \underset{x,y}{min}f(x,y) \\ s.t.\{\begin{array}{l}Ax=0,By=0\\ y_j\le \lfloor y_j^{\ast }\rfloor \\ x\in R^{n_1},y\in R^{n_2}\end{array} \end{gathered}$$

这样我们就有了两个新的节点，接下来只要递归的对这两个节点继续分支限界就可以了，直到获得整数解或无解就停止。如图

搜索树

这样就构成了一颗搜索树。注意这棵树有这样几个特点

1. 由于分支限界是不断进行的，我们一直在添加约束，所以目标函数值一定是在不断增大的，后面的节点目标函数值一定大于前面节点（父节点，祖先节点）的目标函数值
2. 构成方式是不唯一的，因为每次求解得到的$$中非整数变量可能不止一个，可以选取其中任意一个进行分支限界
3. 搜索方式是不唯一的，可以使用深度优先搜索（DFS），广度优先搜索（BFS）等多种方式搜索

在搜索的过程中，还需要注意进行剪枝。无论搜索的顺序如何，一旦获得一个可行解，那么它会是解的上界，我们记忆下这个上界。在接下来的搜索过程中，一旦当前的目标函数值超过了上界，就剪掉这棵子树。

分支定价法（Branch and price）

分支定价法其实就是分支定界法+列生成算法。列生成算法的具体描述可以看本专栏之前的文章。

分支定界法中，求解每个节点对应的松弛问题的时候，是直接求解的。而分支定价法中使用列生成算法来求解。其好处是显然的，列生成算法在变量很多的情况比普通的单纯形法有更好的性能。而且，在解决某个节点的RMP的时候，可以不用重新构建问题，运行一次完整的列生成算法，而是继承父节点的RMP问题，并添加约束，这可能会进一步的加速求解过程。