整数规划
Integer Programming
wangzf / 2024-08-28
整数规划简介
通常，决策变量的取值是大于或等于 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
上面的代码很简单，基本与线性规划的代码一样，不同之处在于， 定义变量时线性规划不限定变量的类型，而整数规划中限定变量类型为整数。