整数规划简介
通常，决策变量的取值是大于或等于 0 的自然数，然而在许多实际问题中，
都要求决策变量的取值为正整数，如机器台数、商品数量、工人数量、装载货物的汽车数量等，
这类要求变量为整数的问题称为
整数规划(Integer Progamming, IP) 问题。
如果只要求一部分决策变量取整数，则称为
混合整数规划(Mix Integer Programming, MIP)；
如果决策变量的取值只能是 0 或 1，则称为
0-1 整数规划(Binary Integer Programming, BIP)；
如果模型是线性模型，则称为
整数线性规划(Integer Linear Programming, ILP)。
整数线性规划
Integer Linear Programming, ILP
$$max Z = 3x_{1} + 2x_{2}$$
$$s.t.\begin{cases} 2x_{1} + 3x_{2} \leq 14 \\ 4x_{1} + 2x_{2} \leq 18 \\ x_{1},x_{2} \geq 0 \text{且为整数} \end{cases}$$
混合整数规划
Mix Integer Programming, MIP
0-1 整数规划
Binray Integer Programming, MIP
整数规划求解
求解整数规划的常用方法有
分支定界法 和 割平面法，
这两种方法的共同特点是：在线性规划的基础上，通过增加附加约束条件，
使整数最优解成为线性规划的一个极点（可行域的一个顶点），于是就可以用单纯形法等方法找到这个最优解，
它们的区别在于约束条件的选取规划和方式不同。
分支定界法
分支定界法（Branch and Bound Algorithm, B&B），
其基本思想是对有整数约束条件问题的可行域进行系统搜索，
通常是把全部解空间反复地切割为越来越小的子集，称为分支，
然后在每个子集内计算出一个目标下界，称为定界。
问题介绍
以最大化目标函数的整数规划（MP）问题 A 为例，最优解为 $Z^{*}_{A}$，如果去掉整数约束，
对应的松弛问题 B 为普通的线性规划问题（LP）。
假设 B 的最优解是 $Z_{B}$，假设某一符合整数约束的 A 问题解（不一定是最优解）为 $Z_{A}$，则有：
$$Z_{A} \leq Z_{B}$$
对松弛问题 B 一个或多个变量添加整数约束（分支），相当于对可行域进行切割，每个可行域空间对应一个线性松弛问题，
设为 $B_{i}$，这些松弛问题 $B_{i}$ 的解的最大值（设为 $Z'_{B}$）一定会小于 $Z_{B}$，
即 $Z'_{B} \leq Z_{B}$，因此 $Z'_{B}$ 是 A 问题的一个上界，即：
$$Z_{A} \leq Z'_{B} \leq Z_{B}$$
同理，这些松弛问题 $B_{i}$ 的解的最小值（设为 $Z''_{B}$）可能会小于 $Z_{A}$，
即 $Z_{A}$ 是 A 问题的一个下界：
$$Z_{A} \leq Z''_{B} \leq Z'_{B} \leq Z_{B}$$
$$Z''_{B} \leq Z_{A} \leq Z'_{B} \leq Z_{B}$$
$$Z_{A} \leq Z_{A}^{*}$$
如果这些最松弛问题 $B_{i}$ 的某个解（设为 $\dot{Z}_{B}$）符合整数约束，
且 $\dot{Z}_{B} > Z_{A}$，则 $\dot{Z}_{B}$ 是 A 问题的一个新的下界。
$$Z_{A} < \dot{Z}_{B} \leq Z_{A}^{*}$$
分支定界法就是将 B 的可行解空间分成子空间再求最大值的方法，逐步减小上界和下界，最终求得 $Z_{A}^{*}$。
当 LP 问题满足全部整数约束条件时，即为 MP 问题的解。
求解步骤
对于上面的整数规划问题 A，求解步骤如下：
去掉整数约束条件，得到原问题 A 的松弛问题 B，使用单纯形法或内点法等求解 B 得到 B 的最优解，即：
$$X^{(0)}=(x_{1}, x_{2})^{T}=(3.25, 2.5)^{T}$$
$$Z^{(0)}=14.75$$
由于此时 $x_{1}$ 和 $x_{2}$ 都不是整数，因此需要选择一个分支变量，如选择 $x_{1}$ 作为分支变量，
分成左支（$x_{1}\leq 3$）和右支（$x_{1}\geq 4$），对应的分支子问题如下：
$LP_{1}$
$$max Z = 3x_{1} + 2x_{2}$$
$$s.t.\begin{cases} 2x_{1} + 3x_{2} \leq 14 \\ 4x_{1} + 2x_{2} \leq 18 \\ x_{1} \leq 3 \\ x_{1},x_{2} \geq 0 \end{cases}$$
$LP_{2}$
$$max Z = 3x_{1} + 2x_{2}$$
$$s.t.\begin{cases} 2x_{1} + 3x_{2} \leq 14 \\ 4x_{1} + 2x_{2} \leq 18 \\ x_{1} \geq 4 \\ x_{1},x_{2} \geq 0 \end{cases}$$
求解两个子问题的最优解（单纯形法、内点法）如下：
$$X^{(1)}=(3.0, 2.66)^{T}, Z^{(1)}=14.33$$
$$X^{(2)}=(4.0, 1.0)^{T}, Z^{(2)}=14.0$$
此时原整数规划 A 的新的下界为 14.0，新的上界为 14.33，即 $14.0 \leq Z^{*} \leq 14.33$。
此时 $LP_{2}$ 的最优解是 14.0，如果继续 $LP_{2}$ 分支，那么其分支后的最优解一定小于 14.0。
因为分支代表更多的约束，使线性规划更逼近整数规划，其最优解小于没有分支的最优解 $Z^{(2)}=14.0$，
所以没有必要对 $LP_{2}$ 这个分支继续搜索，从优化的角度，不可能从这个点以后的分支中找到比目前 14.0 更优的解，
可以直接删除，只需要搜索 $LP_{1}$ 分支即可，这样就大大减少了搜索空间，提高求解的效率。
对 $LP_{1}$ 选择 $x_{2}$ 作为分支变量，分成左支（$x_{2}\leq 2$）和右支（$x_{2} \geq 3$），
对应的分支子问题如下：
$LP_{3}$
$$max Z = 3x_{1} + 2x_{2}$$
$$s.t.\begin{cases} 2x_{1} + 3x_{2} \leq 14 \\ 4x_{1} + 2x_{2} \leq 18 \\ x_{1} \leq 3 \\ x_{2} \leq 2 \\ x_{1},x_{2} \geq 0 \end{cases}$$
$LP_{4}$
$$max Z = 3x_{1} + 2x_{2}$$
$$s.t.\begin{cases} 2x_{1} + 3x_{2} \leq 14 \\ 4x_{1} + 2x_{2} \leq 18 \\ x_{1} \leq 3 \\ x_{2} \geq 3 \\ x_{1},x_{2} \geq 0 \end{cases}$$
求解两个子问题的最优解（单纯形法、内点法）如下：
$$X^{(3)}=(3.0, 2.0)^{T}, Z^{(1)}=13.0$$
$$X^{(4)}=(2.5, 3.0)^{T}, Z^{(2)}=13.5$$
此时可以看到，在第一次分支后的最优解为 $14.0 \leq Z^{*} \leq 14.33$，而在第二次分支后最优解反而小于 14.0，
虽然可以继续在 $LP_{4}$ 分支下继续搜索，但是搜索结果肯定不会大于 $Z^{(2)}=14.0$，只会更差，
而且 $LP_{2}$ 的解恰好满足变量为整数的约束条件，因此该整数规划问题 A 的最优解的 $LP_{2}$ 对应的解为：
$$X^{*}=X^{(2)}=(4.0, 1.0)^{T}, Z^{*}=Z^{(2)}=14.0$$
用图形展示搜索过程如下图：
总结
从分支定界的搜索过程来看，该方法非常简洁清晰，相当于增加约束条件后继续求解普通线性规划问题。
但是也要注意到，在变量很多的情况下，该搜索过程是很复杂的，如对于 0-1 整数规划问题，
每个变量的取值只可能是 0 或 1，分支也只是简单的左右两支，形成简单二叉树。
如果变量个数为 10，那么最小分支数是 1024；如果变量数为 20，那么最小分支数是 1048576，呈指数级增长。
因此，分支定界法一般不考虑直接求解该问题的精确解，而是求解近似解或局部最优解，如可以设定当上界和下界非常接近时（如 0.001），
分支定界结束或者使用相对差值，即分支定界法中的 GAP：
$$GAP = \frac{\bar{Z} - Z}{\bar{Z}}$$
当 $GAP \leq 0.001$ 时，可以认为当前的上界或下界时问题的最优解，分支定界法结束迭代。
割平面法
问题介绍
分支定界法的思路是对原问题对应的松弛问题的可行域进行切割，切割方法是对非整数变量取相邻整数作为附加约束。
从几何的角度来说，这些约束相当于切割可行域的超平面，这些超平面与坐标轴平行。
分支定界法的缺点是子问题由于分支的增加呈指数增长，为克服该缺点，学者提出了割平面法（Cutting Planes Method），
割平面法也是通过增加切割超平面切割掉松弛问题的非整数解部分，但是并没有对问题进行分支。
割平面法通过增加切割超平面切割掉部分的解空间，该超平面应该满足两个条件：
刚好切割掉松弛问题的非整数解部分
保留所有整数解
求解步骤
那如何找到这个切割超平面呢？
假设有如下整数规划问题及其对应的松弛问题：
$$IP: max Z = c^{T}x$$
$$s.t.\begin{cases} Ax = b \\ x \geq 0 \\ x 为整数 \end{cases}$$
$$LP: max Z = c^{T}x$$
$$s.t.\begin{cases} Ax = b \\ x \geq 0 \\ \end{cases}$$
假设 LP 的最优解不是整数解，否则 LP 的最优解就是问题 IP 的最优解。设 LP 的最优解为：
$$X^{(0)} = (b_{1}, \cdots, b_{i}, \cdots, b_{m}, 0, \cdots, 0)^{T}$$
其中，$b_{i}$ 是分数（不是整数），$X^{(0)}$ 表示 $x_{1}, \cdots, x_{i}, \cdots, x_{m}$ 是基变量，
$x_{m+1}, \cdots, x_{n}$ 是非基变量，在单纯形法中说过，在标准型线性规划方程中，非基变量为 0 时，
基变量的值等于常数项，所有基变量组成一个单位阵。
变量
$x_{1}$
$\cdots$
$x_{i}$
$\cdots$
$x_{m}$
$x_{m+1}$
$\cdots$
$x_{n}$
$b$
$x_{1}$
1
$\cdots$
1
$x_{i}$
1
$a_{im+1}$
$\cdots$
$a_{in}$
$b_{i}$
$\cdots$
1
$x_{m}$
1
$b_{i}$ 所在行的方程是：
$$x_{i}+a_{im+1}x_{m+1}+\cdots+a_{im+j}x_{m+j}+\cdots+a_{in}x_{n}=b_{i}$$
$$\Rightarrow x_{i}+\sum_{j=1}^{n-m}a_{im+j}x_{m+j}=b_{i}$$
把 $a_{im+j}$ 和 $b_{i}$ 分解成整数 $N$ 和小数 $f$ 两部分（如 $2.3=2+0.3$），即：
$$a_{im+j}=N_{im+j}+f_{im+j}$$
$$b_{i}=N_{bi}+f_{bi}$$
因此，$b_{i}$ 所在的方程可以写成：
$$x_{i}+\sum_{j=1}^{n-m}(N_{im+j}+f_{im+j})x_{m+j}=N_{bi}+f_{bi}$$
$$x_{i}+\sum_{j=1}^{n-m}N_{im+j}x_{m+j}+\sum_{j=1}^{n-m}f_{im+j}x_{m+j}=N_{bi}+f_{bi}$$
$$x_{i}-N_{bi}+\sum_{j=1}^{n-m}N_{im+j}x_{m+j}=f_{bi}-\sum_{j=1}^{n-m}f_{im+j}x_{m+j}$$
因为 $-\sum_{j=1}^{n-m}f_{im+j}x_{m+j} \leq 0$，$f_{bi}\leq 0$，所以：
$$f_{bi}-\sum_{j=1}^{n-m}f_{im+j}x_{m+j}\leq 1$$
若要决策变量都取整数，则：
$$f_{bi}-\sum_{j=1}^{n-m}f_{im+j}x_{m+j}\leq 0$$
这样就得到第 $i$ 行对应的割平面法方程：
$$f_{bi}-\sum_{j=1}^{n-m}f_{im+j}x_{m+j}\leq 0$$
引入松弛变量 $y_{i}$，将割平面法方程标准化，即：
$$-\sum_{j=1}^{n-m}f_{im+j}x_{m+j}+y_{i}=-f_{bi}$$
将新的约束加入到原来的问题约束中，继续求解，直到求出整数最优解为顶点时才停止计算。
求解步骤示例
$$max Z = 7x_{1} + 9x_{2}$$
$$s.t.\begin{cases} -\frac{1}{3}x_{1} + x_{2} \leq 2.0 \\ x_{1} + \frac{1}{7}x_{2} \leq 5.0 \\ x_{1},x_{2} \geq 0 \text{且为整数} \end{cases}$$
对应的松弛问题为：
$$max Z = 7x_{1} + 9x_{2}$$
$$s.t.\begin{cases} -\frac{1}{3}x_{1} + x_{2} + x_{3} = 2.0 \\ x_{1} + \frac{1}{7}x_{2} + x_{4} = 5.0 \\ x_{1},x_{2}, x_{3}, x_{4} \geq 0 \end{cases}$$
使用单纯形法求解，最优单纯形法如下表：
目标和基变量
b
$x_{1}$
$x_{2}$
$x_{3}$
$x_{4}$
$Z$
-63
0
0
-$\frac{28}{11}$
-$\frac{15}{11}$
$x_{1}$
$\frac{9}{2}$
1
-$\frac{1}{22}$
$\frac{3}{22}$
$x_{2}$
$\frac{7}{2}$
1
$\frac{7}{22}$
$\frac{1}{22}$
在选择行 $i$ 时，一般选择最大的 $f_{bi}$ 所在的行 $i$。
如果 $f_{bi}$ 相同，那么选择 $\sum_{j=1}^{n-m}f_{im+j}$ 小的所在行 $i$ 构造割平面，
因此选择 $x_{2}$ 所在行构造割平面，即：
$$f_{bi}-\sum_{j=1}^{n-m}f_{im+j}x_{m+j} \leq 0$$
$$\frac{1}{2} \leq \frac{7}{22}x_{3} + \frac{1}{22}x_{4}$$
加入松弛变量，并调整后得到：
$$-\frac{7}{22}x_{3}-\frac{1}{22}x_{4}+y_{1}=\frac{1}{2}$$
将新的约束加入到前面得到的最优单纯形表的最后一列中，如下表：
目标和基变量
b
$x_{1}$
$x_{2}$
$x_{3}$
$x_{4}$
$y_{1}$
$Z$
-63
0
0
-$\frac{28}{11}$
-$\frac{15}{11}$
0
$x_{1}$
$\frac{9}{2}$
1
-$\frac{1}{22}$
$\frac{3}{22}$
0
$x_{2}$
$\frac{7}{2}$
1
$\frac{7}{22}$
$\frac{1}{22}$
0
$y_{1}$
-$\frac{1}{2}$
0
0
-$\frac{7}{22}$
-$\frac{1}{22}$
1
使用对偶单纯形法求解，得到最终的最优单纯形表，如下表：
目标和基变量
b
$x_{1}$
$x_{2}$
$x_{3}$
$x_{4}$
$y_{1}$
$Z$
-59
0
0
0
-1
-8
$x_{1}$
$\frac{32}{7}$
1
0
0
$\frac{1}{7}$
-$\frac{1}{7}$
$x_{2}$
3
0
1
0
0
1
$x_{3}$
$\frac{11}{7}$
0
0
1
$\frac{1}{7}$
-$\frac{22}{7}$
选择 $x_{1}$ 所在的行构造割平面，得到割平面方程：
$$\frac{7}{4}\leq \frac{1}{7}x_{4}+\frac{6}{7}y_{1}$$
加入松弛变量，并调整后得到：
$$-\frac{1}{7}x_{4}-\frac{6}{7}y_{1}+y_{2}\leq \frac{7}{4}$$
将新的割平面方程加入到上一步得到的最优单纯形表中，得到如下结果：
目标和基变量
b
$x_{1}$
$x_{2}$
$x_{3}$
$x_{4}$
$y_{1}$
$y_{2}$
$Z$
-59
0
0
0
-1
-8
0
$x_{1}$
$\frac{32}{7}$
1
0
0
$\frac{1}{7}$
-$\frac{1}{7}$
0
$x_{2}$
3
0
1
0
0
1
0
$x_{3}$
$\frac{11}{7}$
0
0
1
$\frac{1}{7}$
-$\frac{22}{7}$
0
$y_{2}$
-$\frac{4}{7}$
0
0
0
-$\frac{1}{7}$
-$\frac{6}{7}$
1
迭代求解得到满足整数规划的解，结果如下表：
目标和基变量
b
$x_{1}$
$x_{2}$
$x_{3}$
$x_{4}$
$y_{1}$
$y_{2}$
$Z$
-55
0
0
0
0
-2
-7
$x_{1}$
4
1
0
0
0
-1
1
$x_{2}$
3
0
1
0
0
1
0
$x_{3}$
1
0
0
1
0
-4
1
$x_{4}$
4
0
0
0
1
6
-7
即得到的满足整数规划的解为：
$$X^{*}=(x_{1}, x_{2}) = (4, 3)$$
$$Z^{*}=55$$
Gurobi 求解整数规划
使用 Gurobi 求解以下整数规划模型：
$$max Z = 3x_{1} + 2x_{2}$$
$$s.t.\begin{cases} 2x_{1} + 3x_{2} \leq 14 \\ 4x_{1} + 2x_{2} \leq 18 \\ x_{1},x_{2} \geq 0 \text{且为整数} \end{cases}$$
import gurobipy as grb
# 定义模型
model = grb.Model()
# 定义整数变量
x1 = model.addVars(vtype = grb.GRB.INTEGER, name = "x1")
x2 = model.addVars(vtype = grb.GRB.INTEGER, name = "x2")
# 添加约束
model.addConstrs(2 * x1 + 3 * x2 <= 14)
model.addConstrs(4 * x1 + 2 * x2 <= 18)
model.addConstrs(x1 >= 0)
model.addConstrs(x2 >= 0)
# 定义目标函数
model.setObjective(3 * x1 + 2 * x2, sense = grb.GRB.MAXIMIZE)
# 模型求解
model.optimize()
# 模型结果打印
print(f"目标函数值：{model.objVal}")
for v in model.getVars():
print(f"参数 {v.varName} = {v.x}")
# 目标函数值：14.0
# 参数 x1 = 4.0
# 参数 x2 = 1.0
上面的代码很简单，基本与线性规划的代码一样，不同之处在于，
定义变量时线性规划不限定变量的类型，而整数规划中限定变量类型为整数。