整数规划简介

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

• 如果只要求一部分决策变量取整数，则称为 混合整数规划(Mix Integer Programming, MIP)；
• 如果决策变量的取值只能是 0 或 1，则称为 0-1 整数规划(Binary Integer Programming, BIP)；
• 如果模型是线性模型，则称为 整数线性规划(Integer Linear Programming, ILP)。

整数线性规划

Integer Linear Programming, ILP

$$maxZ=3x_1+2x_2$$

$$s.t.\{\begin{array}{c}2x_1+3x_2\le 14\\ 4x_1+2x_2\le 18\\ x_1,x_2\ge 0\text{且为整数}\end{array}$$

混合整数规划

Mix Integer Programming, MIP

0-1 整数规划

Binray Integer Programming, MIP

整数规划求解

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

分支定界法

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

问题介绍

以最大化目标函数的整数规划（MP）问题 A 为例，最优解为 $Z_A^{\ast }$，如果去掉整数约束， 对应的松弛问题 B 为普通的线性规划问题（LP）。

假设 B 的最优解是 $Z_B$，假设某一符合整数约束的 A 问题解（不一定是最优解）为 $Z_A$，则有：

$$Z_A\le Z_B$$

对松弛问题 B 一个或多个变量添加整数约束（分支），相当于对可行域进行切割，每个可行域空间对应一个线性松弛问题， 设为 $B_i$，这些松弛问题 $B_i$ 的解的最大值（设为 $Z_B^{\prime }$）一定会小于 $Z_B$， 即 $Z_B^{\prime }\le Z_B$，因此 $Z_B^{\prime }$ 是 A 问题的一个上界，即：

$$Z_A\le Z_B^{\prime }\le Z_B$$

同理，这些松弛问题 $B_i$ 的解的最小值（设为 $Z_B^{\prime \prime }$）可能会小于 $Z_A$， 即 $Z_A$ 是 A 问题的一个下界：

$$Z_A\le Z_B^{\prime \prime }\le Z_B^{\prime }\le Z_B$$ $$Z_B^{\prime \prime }\le Z_A\le Z_B^{\prime }\le Z_B$$ $$Z_A\le Z_A^{\ast }$$

如果这些最松弛问题 $B_i$ 的某个解（设为 ${\dot{Z}}_B$）符合整数约束， 且 ${\dot{Z}}_B>Z_A$，则 ${\dot{Z}}_B$ 是 A 问题的一个新的下界。

$$Z_A<{\dot{Z}}_B\le Z_A^{\ast }$$

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

求解步骤

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

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

$$X^{\left(0\right)}=(x_1,x_2{)}^T=(3.25,2.5{)}^T$$ $$Z^{\left(0\right)}=14.75$$

2. 由于此时 $x_1$ 和 $x_2$ 都不是整数，因此需要选择一个分支变量，如选择 $x_1$ 作为分支变量， 分成左支（$x_1\le 3$）和右支（$x_1\ge 4$），对应的分支子问题如下：

   $L{P}_1$ $$maxZ=3x_1+2x_2$$

   $$s.t.\{\begin{array}{c}2x_1+3x_2\le 14\\ 4x_1+2x_2\le 18\\ x_1\le 3\\ x_1,x_2\ge 0\end{array}$$

   $L{P}_2$ $$maxZ=3x_1+2x_2$$

   $$s.t.\{\begin{array}{c}2x_1+3x_2\le 14\\ 4x_1+2x_2\le 18\\ x_1\ge 4\\ x_1,x_2\ge 0\end{array}$$

   求解两个子问题的最优解（单纯形法、内点法）如下：

   $$X^{\left(1\right)}=(3.0,2.66{)}^T,Z^{\left(1\right)}=14.33$$ $$X^{\left(2\right)}=(4.0,1.0{)}^T,Z^{\left(2\right)}=14.0$$

   此时原整数规划 A 的新的下界为 14.0，新的上界为 14.33，即 $14.0\le Z^{\ast }\le 14.33$。

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

4. 对 $L{P}_1$ 选择 $x_2$ 作为分支变量，分成左支（$x_2\le 2$）和右支（$x_2\ge 3$）， 对应的分支子问题如下：

   $L{P}_3$ $$maxZ=3x_1+2x_2$$

   $$s.t.\{\begin{array}{c}2x_1+3x_2\le 14\\ 4x_1+2x_2\le 18\\ x_1\le 3\\ x_2\le 2\\ x_1,x_2\ge 0\end{array}$$

   $L{P}_4$ $$maxZ=3x_1+2x_2$$

   $$s.t.\{\begin{array}{c}2x_1+3x_2\le 14\\ 4x_1+2x_2\le 18\\ x_1\le 3\\ x_2\ge 3\\ x_1,x_2\ge 0\end{array}$$

   求解两个子问题的最优解（单纯形法、内点法）如下：

   $$X^{\left(3\right)}=(3.0,2.0{)}^T,Z^{\left(1\right)}=13.0$$ $$X^{\left(4\right)}=(2.5,3.0{)}^T,Z^{\left(2\right)}=13.5$$

5. 此时可以看到，在第一次分支后的最优解为 $14.0\le Z^{\ast }\le 14.33$，而在第二次分支后最优解反而小于 14.0， 虽然可以继续在 $L{P}_4$ 分支下继续搜索，但是搜索结果肯定不会大于 $Z^{\left(2\right)}=14.0$，只会更差， 而且 $L{P}_2$ 的解恰好满足变量为整数的约束条件，因此该整数规划问题 A 的最优解的 $L{P}_2$ 对应的解为：

   $$X^{\ast }=X^{\left(2\right)}=(4.0,1.0{)}^T,Z^{\ast }=Z^{\left(2\right)}=14.0$$

用图形展示搜索过程如下图：

总结

从分支定界的搜索过程来看，该方法非常简洁清晰，相当于增加约束条件后继续求解普通线性规划问题。 但是也要注意到，在变量很多的情况下，该搜索过程是很复杂的，如对于 0-1 整数规划问题， 每个变量的取值只可能是 0 或 1，分支也只是简单的左右两支，形成简单二叉树。 如果变量个数为 10，那么最小分支数是 1024；如果变量数为 20，那么最小分支数是 1048576，呈指数级增长。

因此，分支定界法一般不考虑直接求解该问题的精确解，而是求解近似解或局部最优解，如可以设定当上界和下界非常接近时（如 0.001）， 分支定界结束或者使用相对差值，即分支定界法中的 GAP：

$$GAP=\frac{\overline{Z}-Z}{\overline{Z}}$$

当 $GAP\le 0.001$ 时，可以认为当前的上界或下界时问题的最优解，分支定界法结束迭代。

割平面法

问题介绍

分支定界法的思路是对原问题对应的松弛问题的可行域进行切割，切割方法是对非整数变量取相邻整数作为附加约束。 从几何的角度来说，这些约束相当于切割可行域的超平面，这些超平面与坐标轴平行。

分支定界法的缺点是子问题由于分支的增加呈指数增长，为克服该缺点，学者提出了割平面法（Cutting Planes Method）， 割平面法也是通过增加切割超平面切割掉松弛问题的非整数解部分，但是并没有对问题进行分支。

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

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

求解步骤

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

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

$$IP:maxZ=c^{T}x$$ $$s.t.\{\begin{array}{c}Ax=b\\ x\ge 0\\ x为整数\end{array}$$

$$LP:maxZ=c^{T}x$$ $$s.t.\{\begin{array}{c}Ax=b\\ x\ge 0\end{array}$$

假设 LP 的最优解不是整数解，否则 LP 的最优解就是问题 IP 的最优解。设 LP 的最优解为：

$$X^{\left(0\right)}=(b_1,\cdots ,b_i,\cdots ,b_m,0,\cdots ,0{)}^T$$

其中，$b_i$ 是分数（不是整数），$X^{\left(0\right)}$ 表示 $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}\le 0$，$f_{bi}\le 0$，所以：

$$f_{bi}-\sum _{j=1}^{n-m}{f}_{im+j}{x}_{m+j}\le 1$$

若要决策变量都取整数，则：

$$f_{bi}-\sum _{j=1}^{n-m}{f}_{im+j}{x}_{m+j}\le 0$$

这样就得到第 $i$ 行对应的割平面法方程：

$$f_{bi}-\sum _{j=1}^{n-m}{f}_{im+j}{x}_{m+j}\le 0$$

引入松弛变量 $y_i$，将割平面法方程标准化，即：

$$-\sum _{j=1}^{n-m}{f}_{im+j}{x}_{m+j}+y_i=-f_{bi}$$

将新的约束加入到原来的问题约束中，继续求解，直到求出整数最优解为顶点时才停止计算。

求解步骤示例

$$maxZ=7x_1+9x_2$$

$$s.t.\{\begin{array}{c}-\frac{1}{3}{x}_1+x_2\le 2.0\\ x_1+\frac{1}{7}{x}_2\le 5.0\\ x_1,x_2\ge 0\text{且为整数}\end{array}$$

对应的松弛问题为：

$$maxZ=7x_1+9x_2$$

$$s.t.\{\begin{array}{c}-\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\ge 0\end{array}$$

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

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

$$\frac{1}{2}\le \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}\le \frac{1}{7}{x}_4+\frac{6}{7}{y}_1$$

加入松弛变量，并调整后得到：

$$-\frac{1}{7}{x}_4-\frac{6}{7}{y}_1+y_2\le \frac{7}{4}$$

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

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

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

$$X^{\ast }=(x_1,x_2)=(4,3)$$ $$Z^{\ast }=55$$

Gurobi 求解整数规划

使用 Gurobi 求解以下整数规划模型：

$$maxZ=3x_1+2x_2$$

$$s.t.\{\begin{array}{c}2x_1+3x_2\le 14\\ 4x_1+2x_2\le 18\\ x_1,x_2\ge 0\text{且为整数}\end{array}$$

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

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