整数规划

通常，决策变量的取值是大于或等于 0 的自然数，然而在许多实际问题中， 都要求决策变量的取值为正整数，如机器台数、商品数量、工人数量、装载货物的汽车数量等， 这类要求变量为整数的问题称为 整数规划(Integer Progamming, IP) 问题。

• 如果只要求一部分决策变量取整数，则称为 混合整数规划(Mix Integer Programming, MIP)；
• 如果决策变量的取值只能是 0 或 1，则称为 0-1 整数规划(Binary Integer Programming, BIP)；
• 如果模型是线性模型，则称为 整数线性规划(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}$$

整数规划的求解方式

求解整数规划的常用方法有 分支定界法 和 割平面法， 这两种方法的共同特点是：在线性规划的基础上，通过增加附加约束条件， 使整数最优解成为线性规划的一个极点（可行域的一个顶点）， 于是就可以用单纯形法等方法找到整个最优解， 它们的区别在于约束条件的选取规划和方式不同。

分支定界法

分支定界法（Branch and Bound Algorithm, B&B）， 其基本思想是对有整数约束条件问题的可行域进行系统搜索， 通常是把全部解空间反复地切割为越来越小的子集，称为分支， 然后在每个子集内计算出一个目标下界，称为定界。

问题介绍

以最大化目标函数的整数规划（MP）问题 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}$ 是 MP 问题的一个上界， 同理，这些松弛问题 $B_{i}$ 的解的最小值（设为 $Z''_{B}$）可能会小于 $Z_{A}$， 即 $Z_{A}$ 是 MP 问题的一个下界，如果这些最松弛问题 $B_{i}$ 的某个解（设为 $\dot{Z}_{B}$）符合整数约束， 且 $\dot{Z}_{B} > Z_{A}$，则 $\dot{Z}_{B}$ 是 MP 问题的一个新的下界。

分支定界法就是将 B 的可行解空间分成子空间再求最大值的方法，逐步减小上界和下界，最终求得 $Z_{B}^{*}$。 当 LP 问题满足全部整数约束条件时，即为 MP 问题的解。

求解步骤

对于上面的整数规划问题 A，求解步骤如下：

1. 去掉整数约束条件，得到原问题 A 的松弛问题 B，使用单纯形法或内点法等求解 B 得到 B 的最优解，即：

$$X^{(0)}=(x_{1}, x_{2})^{T}=(3.25, 2.5)^{T}$$ $$Z^{(0)}=14.75$$

2. 由于此时 $x_{1}$ 和 $x_{2}$ 都不是整数，因此需要选择一个分支变量，如选择 $x_{1}$ 作为分支变量， 分成左支（$x_{3}\leq 3$）和右支（$x_{4}\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$。

3. 此时 $LP_{2}$ 的最优解是 14.0，如果继续 $LP_{2}$ 分支，那么其分支后的最优解一定小于 14.0。 因为分支代表更多的约束，使线性规划更逼近整数规划，其最优解小于没有分支的最优解 $Z^{(2)}=14.0$， 所以没有必要对 $LP_{2}$ 这个分支继续搜索，从优化的角度，不可能从这个点以后的分支中找到比目前 14.0 更优的解， 可以直接删除，只需要搜索 $LP_{1}$ 分支即可，这样就大大减少了搜索空间，提高求解的效率。
4. 对 $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$$

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）， 割平面法也是通过增加切割超平面切割掉松弛问题的非整数解部分，但是并没有对问题进行分支。

割平面法通过增加切割超平面切割掉部分的解空间，该超平面应该满足两个条件：

1. 刚好切割掉松弛问题的非整数解部分
2. 保留所有整数解

求解步骤

那如何找到这个切割超平面呢？

假设有如下整数规划问题及其对应的松弛问题：

$$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 时， 基变量的值等于常数项，所有基变量组成一个单位阵。

$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}$$

使用单纯形法求解，最优单纯形法如下表：

在选择行 $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}$$

将新的约束加入到前面得到的最优单纯形表的最后一列中，如下表：

使用对偶单纯形法求解，得到最终的最优单纯形表，如下表：

选择 $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}$$

将新的割平面方程加入到上一步得到的最优单纯形表中，得到如下结果：

迭代求解得到满足整数规划的解，结果如下表：

即得到的满足整数规划的解为：

$$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

上面的代码很简单，基本与线性规划的代码一样，不同之处在于， 定义变量时线性规划不限定变量的类型，而整数规划中限定变量类型为整数。