整数规划-割平面法

割平面法思想

在之前，梳理了分支定界法的流程:分支定界法
除了分支定界法，割平面法也是求解整数规划的另一个利器。
我们已经知道，线性规划的可行域是一个凸集，而最优点将会在凸集的某个顶点处取到。而如果凸集的顶点都是整数点，那这样的话只要使用单纯形法即可求得整数最优解。

就像下图的凸包所示，在实际情况中，线性规划的可行域往往交点都不在整数点处，如果能找到整数点的一个凸包，那整数规划问题即可转化为普通的线性规划问题。但是想找到这样的一个凸包是非常困难的，只能使用某种方法去不断的逼近这个凸包。

这就是割平面法的思想：不断地向原问题中添加约束去逼近这个整数凸包，从而使得解出来的解为整数解。

Gomory’s割平面法原理

在上面提到了，通过不断添加约束去逼近一个整数凸包，那么该如何去添加约束呢？也就是如何确定割平面这是本部分的重点。
确定割平面的算法有很多，暂时先以较为基础的Gomory’s 分数割平面算法介绍，后续如果用到更多其他割平面再进行补充。
先看一个标准整数规划问题
$$\begin{array}{rl}min& {\mathbf{c}}^T\mathbf{x}\\ s.t.& \{\begin{array}{l}\mathbf{Ax}=\mathbf{b}\\ \mathbf{x}\ge 0\\ \mathbf{x}\in {\mathbb{Z}}^n\end{array}\end{array}$$

当使用单纯形法求解整数规划问题时，可以将问题划分为基变量（Basic Variables）和非基变量（Non-Basic Variables）。在标准形式的整数规划问题中，可以进行如下的续写：
令基变量为 ${\mathbf{x}}_B$，非基变量为 ${\mathbf{x}}_N$。整数规划问题可以表示为：
$$\min {\mathbf{c}}^T\mathbf{x}={\mathbf{c}}_B^T{\mathbf{x}}_B+{\mathbf{c}}_N^T{\mathbf{x}}_N$$
约束条件：
$$\begin{array}{rl}\mathbf{B}{\mathbf{x}}_B+\mathbf{N}{\mathbf{x}}_N& =\mathbf{b}\\ {\mathbf{x}}_B,{\mathbf{x}}_N& \ge 0\\ \mathbf{x}& \in {\mathbb{Z}}^n\end{array}$$
其中：

• ${\mathbf{c}}^T=[{\mathbf{c}}_B^T,{\mathbf{c}}_N^T]$ 是目标函数的系数向量，${\mathbf{c}}_B$ 对应基变量的系数，${\mathbf{c}}_N$ 对应非基变量的系数。
• $\mathbf{B}$ 和 $\mathbf{N}$ 分别是基变量和非基变量对应的约束矩阵的子矩阵。
• ${\mathbf{x}}_B$ 和 ${\mathbf{x}}_N$ 分别是基变量和非基变量向量。

现在将整数约束松弛掉，使用单纯形法进行求解，多次迭代后模型收敛。收敛后的问题可以表述如下:

$\min f_0+{\mathbf{c}}_N^T{\mathbf{x}}_N$
约束条件：
$$\begin{array}{rl}{\mathbf{x}}_B+{\mathbf{B}}^{-1}\mathbf{N}{\mathbf{x}}_N& ={\mathbf{B}}^{-1}\mathbf{b}\\ {\mathbf{x}}_B,{\mathbf{x}}_N& \ge 0\end{array}$$
其中$f_0={\mathbf{c}}_B^T{\mathbf{x}}_B$在求解之后为一个常数。
那么将上述约束变形即可得到${\mathbf{x}}_B+\lfloor {\mathbf{B}}^{-1}\mathbf{N}\rfloor {\mathbf{x}}_N\le \lfloor {\mathbf{B}}^{-1}\mathbf{b}\rfloor$将其与原约束相减可以得到
$$({\mathbf{B}}^{-1}\mathbf{N}-\lfloor {\mathbf{B}}^{-1}\mathbf{N}\rfloor ){\mathbf{x}}_N\ge {\mathbf{B}}^{-1}\mathbf{b}-\lfloor {\mathbf{B}}^{-1}\mathbf{b}\rfloor$$
这个约束可以割掉小数解得部分，原因如下。
如果最终解出来的仍为小数解，表示为[$x_B,x_N$],其中$x_B$为小数解，$x_N=0$,那么就有${\mathbf{B}}^{-1}\mathbf{b}$也为小数，那么就有${\mathbf{B}}^{-1}\mathbf{b}-\lfloor {\mathbf{B}}^{-1}\mathbf{b}\rfloor >0$,而$x_N=0$就导致不等式右边大于0，不等式左边等于0.不等式不成立。因此为了使不等式成立，就需要满足最终的解为不能有小数解。

实例

$$\begin{array}{rl}max& z=4x_1-x_2\\ s.t.& \{\begin{array}{l}7x_1-2x_2\le 14\\ x_2\le 3\\ 2x_1-2x_2\le 3\\ x_1,x_2\ge 0\\ \mathbf{x}\in {\mathbb{Z}}^n\text{(整数限制)}\end{array}\end{array}$$
可行域如下

求解松弛子问题1

$$\begin{array}{rl}max& z=4x_1-x_2\\ s.t.& \{\begin{array}{l}7x_1-2x_2+x_3=14\\ x_2+x_4=3\\ 2x_1-2x_2+x_5=3\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{array}\end{array}$$
求解得到

Optimal objective value: 8.428571428571429
x1: 2.857142857142857
x2: 3.0
x3: 0.0
x4: 0.0
x5: 3.2857142857142865

以x1,x2,x5作为基变量，对约束进行等价变换(把约束中基变量的系数矩阵变为单位阵)，变换之后的问题如下
$$\begin{array}{rl}max& z=4x_1-x_2\\ s.t.& \{\begin{array}{l}1x_1+0x_2+\frac{1}{7}{x}_3+\frac{2}{7}{x}_4+0x_5=\frac{20}{7}\\ 0x_1+1x_2+0x_3+1x_4+0x_5=3\\ 0x_1+0x_2-\frac{2}{7}{x}_3+\frac{10}{7}{x}_4+1x_5=\frac{23}{7}\\ x_1,x_2,x_3,x_4,x_5\ge 0\end{array}\end{array}$$
选择第一个约束，构造得到割平面不等式$\frac{1}{7}{x}_3+\frac{2}{7}{x}_4\ge \frac{6}{7}$将这个约束化为标准形式$\frac{1}{7}{x}_3+\frac{2}{7}{x}_4-s=\frac{6}{7}$加入到原问题中得到子问题2。
$$\begin{array}{rl}max& z=4x_1-x_2\\ s.t.& \{\begin{array}{l}1x_1+0x_2+\frac{1}{7}{x}_3+\frac{2}{7}{x}_4+0x_5=\frac{20}{7}\\ 0x_1+1x_2+0x_3+1x_4+0x_5=3\\ 0x_1+0x_2-\frac{2}{7}{x}_3+\frac{10}{7}{x}_4+1x_5=\frac{23}{7}\\ \frac{1}{7}{x}_3+\frac{2}{7}{x}_4-s=\frac{6}{7}\\ x_1,x_2,x_3,x_4,x_5,s\ge 0\end{array}\end{array}$$
求解得到

Optimal objective value: 7.500000000000002
x1: 2.0000000000000004
x2: 0.5000000000000004
x3: 1.0000000000000004
x4: 2.4999999999999996
x5: 0.0
s: 0.0

选择x1,x2,x3,x4作为基变量，继续对约束进行等价变换。
变换之后的问题如下：

$$\begin{array}{rl}max& z=4x_1-x_2\\ s.t.& \{\begin{array}{l}1x_1+0x_2+0x_3+0x_4+0x_5+1s=2\\ 0x_1+1x_2+0x_3+0x_4-\frac{1}{2}{x}_5+1s=\frac{1}{2}\\ 0x_1+0x_2+1x_3+0x_4-1x_5-5s=1\\ 0x_1+0x_2+0x_3+1x_4+\frac{1}{2}{x}_5-1s=\frac{5}{2}\\ x_1,x_2,x_3,x_4,x_5,s\ge 0\end{array}\end{array}$$
选择第二个继续构造不等式得到$\frac{1}{2}{x}_5\ge \frac{1}{2}$标准化之后为$\frac{1}{2}{x}_5-s_1=\frac{1}{2}$加入到原问题中得到子问题3：
$$\begin{array}{rl}max& z=4x_1-x_2\\ s.t.& \{\begin{array}{l}1x_1+0x_2+0x_3+0x_4+0x_5+1s=2\\ 0x_1+1x_2+0x_3+0x_4-\frac{1}{2}{x}_5+1s=\frac{1}{2}\\ 0x_1+0x_2+1x_3+0x_4-1x_5-5s=1\\ 0x_1+0x_2+0x_3+1x_4+\frac{1}{2}{x}_5-1s=\frac{5}{2}\\ \frac{1}{2}{x}_5-s_1=\frac{1}{2}\\ x_1,x_2,x_3,x_4,x_5,s\ge 0\end{array}\end{array}$$
求解得到

Optimal objective value: 7.0
x1: 2.0
x2: 1.0
x3: 2.0
x4: 2.0
x5: 1.0
s: 0.0
s1: 0.0

得到了整数解。

博客中涉及到的代码