考虑如下的整数规划问题。
$$
\begin{aligned}
\max~ & c^Tx \\
& Ax = b\\
& x\geq 0\\
& x\in \mathbb{Z}^n
\end{aligned}
$$
其中 $A\in\mathbb{R}^{m\times n}, b\in\mathbb{R}^m, c\in \mathbb{R}^n$。
对应的线性规划问题称为它的松弛问题。割平面法就是对松弛问题求解。如果最优解不是整数解，就增加新的约束，直到获得整数解。
从几何角度来看，等式可以看成超平面。一个不等式相当于把一个空间切分成两半，然后取其中一半。这样一来，可以通过增加约束，切掉非整数解。
这样的不等式也称为 割平面（Cutting Plane）。
介绍一种构造割平面的方法，称为 Gomory-Chvátal Cut，简称 GC 割。
回顾单纯形算法，我们可以把约束条件用分块矩阵表示。令 $B$ 和 $N$ 代表基矩阵和非基矩阵，$x_B, x_N$ 代表对应的基变量和非基变量。约束条件可以写成
$$
x_B + B^{-1}Nx_N = B^{-1}b
$$
令 $\tilde{b} = B^{-1}b$。令 $J$ 代表非基变量的下标。再把 $B^{-1}N$ 写成列向量的形式。
$$
B^{-1}N = [\tilde{a}_{j} ], \quad j\in J
$$
我们有
$$
x_B + \sum_{j\in J}\tilde{a}_{j} x_j = \tilde{b}
$$
把上式中 $\tilde{a}_j$ 向下取整，我们有
$$
x_B + \sum_{j\in J} \lfloor \tilde{a}_j \rfloor x_j \leq \tilde{b}
$$
由于 $x$ 是可行解，那么它的分量都是整数。因此，不等式的左边是整数向量。那么，对不等式右边的向量 $\tilde{b}$ 进行取整，不等式依然成立。
我们得到
$$
x_B + \sum_{j\in J} \lfloor \tilde{a}_j \rfloor x_j \leq \lfloor\tilde{b}\rfloor
$$
由于 $x_B= \tilde{b} - \sum_{j\in J}\tilde{a}_{j} x_j$，代入上式得到 GC 割。
$$
\sum_{j\in J}(\tilde{a}_j-\lfloor \tilde{a}_j\rfloor) x_j \geq \tilde{b} - \lfloor\tilde{b}\rfloor
$$
$$
\begin{aligned}
\max~ & 4x_1+5x_2\\
\text{s.t. } & x_1+4x_2 \leq 10\\
& 3x_1-4x_2 \leq 6\\
& x_1, x_2 \in \mathbb{Z}_+
\end{aligned}
$$
它的松弛问题如下
$$
\begin{aligned}
\max~ & 4x_1+5x_2\\
\text{s.t. } & x_1+4x_2 \leq 10\\
& 3x_1-4x_2 \leq 6\\
& x_1, x_2 \geq 0
\end{aligned}
$$
先引入松弛变量 $x_3, x_4$，把上面的不等式写成等式形式。
$$
\begin{aligned}
\max~ & 4x_1+5x_2\\
\text{s.t. } & x_1+4x_2 + x_3 = 10\\
& 3x_1-4x_2 + x_4 = 6\\
& x_1, x_2, x_3, x_4 \geq 0
\end{aligned}
$$
它的最优解为 $x_1=4, x_2=1.5$。
$$
\begin{aligned}
& B^{-1}N = \begin{bmatrix}
\tilde{a}_3 & \tilde{a}_4
\end{bmatrix} =
\begin{bmatrix}
-0.0625 & 0.1875\\
0.25 & 0.25
\end{bmatrix}\\[6pt]
& \tilde{b} = B^{-1}b =
\begin{bmatrix}
1.5\\
4
\end{bmatrix}
\end{aligned}
$$
接下来对向量进行取整，并计算它们的差值。
$$
\begin{aligned}
& \tilde{a}_3 -\lfloor\tilde{a}_3\rfloor =
\begin{bmatrix}
-0.0625\\
0.25
\end{bmatrix}
- \begin{bmatrix}
-1\\
0
\end{bmatrix}=\begin{bmatrix}
0.9375\\
0.25
\end{bmatrix}\\[6pt]
& \tilde{a}_4 -\lfloor\tilde{a}_4\rfloor =
\begin{bmatrix}
0.1875\\
0.25
\end{bmatrix}
- \begin{bmatrix}
0\\
0
\end{bmatrix}=\begin{bmatrix}
0.1875\\
0.25
\end{bmatrix}\\[6pt]
& \tilde{b} -\lfloor\tilde{b}\rfloor =
\begin{bmatrix}
1.5\\
4
\end{bmatrix}
- \begin{bmatrix}
1\\
4
\end{bmatrix}=\begin{bmatrix}
0.5\\
0
\end{bmatrix}
\end{aligned}
$$
再把结果代入下面的不等式。
$$
(\tilde{a}_3-\lfloor \tilde{a}_3\rfloor) x_3 + (\tilde{a}_4-\lfloor \tilde{a}_4 \rfloor ) x_4 \geq \tilde{b}-\lfloor \tilde{b} \rfloor
$$
我们得到
$$
\begin{bmatrix}
0.9375\\
0.25
\end{bmatrix}x_3 +
\begin{bmatrix}
0.1875\\
0.25
\end{bmatrix}x_4
\geq \begin{bmatrix}
0.5\\
0
\end{bmatrix}
$$
即
$$
\begin{aligned}
& 0.9375x_3 + 0.1875 x_4 \geq 0.5\\
& 0.25 x_3 + 0.25 x_4 \geq 0 \\
\end{aligned}
$$
把它们添加到松弛问题中，引入松弛变量改写成等式。然后重复上面的步骤，直到得到整数解。
简要描述算法步骤。
第 0 步：初始化
考虑如下松弛问题。
$$
\begin{aligned}
\max~ & c^Tx \\
& Ax = b\\
& x\geq \mathbf{0}\\
\end{aligned}
$$
第 1 步：求解
求解松弛问题。如果得到整数解，它就是最优解。算法停止，并返回最优解。否则执行下一步。
第 2 步：生成割平面
计算基矩阵 $B$ 和非基矩阵 $N$。注意，如果存在冗余的约束，需要先删除对应的行。比如，最优解对应的基列是 $\set{1, 3}$，但此时系数矩阵 $A$ 有三行，那么第 $2$ 行是冗余的。
接下来计算 $\tilde{a}_j, \tilde{b}$，从而得到下面的不等式。
$$
\sum_{j\in J}(\tilde{a}_j-\lfloor \tilde{a}_j\rfloor) x_j \geq \tilde{b} - \lfloor\tilde{b}\rfloor
$$
第3步：添加割平面
引入松弛变量 $s$，把不等式改写成等式。
$$
\sum_{j\in J}(\tilde{a}_j-\lfloor \tilde{a}_j\rfloor) x_j - s = \tilde{b} - \lfloor\tilde{b}\rfloor
$$
令 $f_j := \tilde{a}_j-\lfloor \tilde{a}_j\rfloor$，$f:=\tilde{b} - \lfloor\tilde{b}\rfloor$，上式可以写成
$$
\sum_{j\in J}f_j x_j - s = f
$$
令 $F = [f_j]_{j\in N}$，$\mathbf{I}$ 为单位矩阵，我们有
$$
F x_n - \mathbf{I}\cdot s = f
$$
把它添加到松弛问题中得到
$$
\begin{aligned}
\max~ & c^Tx + \mathbf{0}^Ts \\
& Ax + s = b\\
& F x_n - \mathbf{I}\cdot s = f\\
& x, s\geq \mathbf{0}\\
\end{aligned}
$$
再执行 第 1 步。