整数规划
- 对比线性规划是连续变量的线性优化问题，整数规划其实就是整数变量的优化问题，研究比较多的是纯整数线性规划或者混合整数线性规划（MILP），区别于线性规划，整数规划强调的是决策变量的取值必须是整数。解线性规划的方法不能保证求出的解满足整数条件，因此引出来求解整数规划的对应方法，比较常见的是分支定界与割平面法。另外一些方法先留一下，随后再总结。
分支定界法
- 分支定界：Branch and bound
- 从方法命名上其实就能看出一些问题，核心的点就是两个：分支、定界。
- 方法的思路：假设一个整数规划的问题是A，去除整数这个约束可以得到与这个命题相对应的线性规划命题B，首先从解命题B开始，如果求出的最优解不满足整数条件，那么这个最优解可以看作是命题A的上界 z ‾ \overline z z，而问题A的任何一个可行解都可以作为一个下界 z ‾ \underline z z。分支定界的目的其实就是不断的将B问题进行划分以降低上界，增加下界，知道找到最优解 z ∗ z^* z∗。
- 解命题B的线性优化命题就可以使用单纯形法进行解决。
eg：
m
a
x
z
=
40
x
1
+
90
x
2
s
.
t
.
9
x
1
+
7
x
2
≤
56
7
x
1
+
20
x
2
≤
70
x
1
,
x
2
≥
0
x
1
,
x
2
整
数
\begin{aligned} &max&z = 40x_1 +90x_2\\ &s.t. &9x_1 +7x_2 \leq56\\ & &7x_1 +20x_2 \leq70\\ & &x_1,x_2 \geq0\\ & &x_1,x_2 整数\\ \end{aligned}
maxs.t.z=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0x1,x2整数
命题A可以看作是原问题，命题B可以看作是去除了最后一个 x 1 , x 2 整 数 x_1,x_2 整数 x1,x2整数的约束条件后的问题
- 首先求解B问题，二元的优化命题可以直接利用图解法进行求解，得到的最优解： x 1 = 4.81 , x 2 = 1.82 , z 0 = 356 x_1=4.81,x_2=1.82,z_0=356 x1=4.81,x2=1.82,z0=356
- 从求解的结果上看，决策变量取值不满足整数约束，但是最终求出的目标函数值 z 0 = 356 z_0=356 z0=356可以看作是问题A的上界 z ‾ = 356 \overline z=356 z=356，从约束看，很容易找到一个下界限就是 x 1 = 0 , x 2 = 0 , z ‾ = 0 x_1=0,x_2=0,\underline z=0 x1=0,x2=0,z=0.
- 下一步就是针对不满足整数条件变量进行分支，基于变量 x 1 x_1 x1可以分为两个部分{ B 1 : x 1 ≤ 4 ; B 2 : x 2 ≥ 5 ; B_1:x_1\leq4;B_2:x_2\geq5; B1:x1≤4;B2:x2≥5;}，分别针对两个分支进行求解，得到如下的结果：
| B 1 B_1 B1 | B 2 B_2 B2 |
|---|---|
| z 1 = 349 ; x 1 = 4 ; x 2 = 2.1 z_1=349;x_1=4;x_2=2.1 z1=349;x1=4;x2=2.1 | z 2 = 341 ; x 1 = 5 ; x 2 = 1.57 z_2=341;x_1=5;x_2=1.57 z2=341;x1=5;x2=1.57 |
- 通过上述解可以重新更新上界 z ‾ = 349 \overline z=349 z=349，下界仍然不变，在这个基础上重新进行分支，分别对 B 1 B_1 B1问题进行分支{ B 3 : x 2 ≤ 2 ; B 4 : x 2 ≥ 3 ; B_3:x_2\leq2;B_4:x_2\geq3; B3:x2≤2;B4:x2≥3;}以及对 B 2 B_2 B2问题进行分支{ B 5 : x 1 ≤ 1 ; B 6 : x 2 ≥ 2 ; B_5:x_1\leq1;B_6:x_2\geq2; B5:x1≤1;B6:x2≥2;}
- 求解上述问题，有如下的结果：
| B 3 B_3 B3 | B 4 B_4 B4 | B 5 B_5 B5 | B 6 B_6 B6 |
|---|---|---|---|
| z 3 = 340 ; x 1 = 4 ; x 2 = 2 z_3=340;x_1=4;x_2=2 z3=340;x1=4;x2=2 | z 2 = 327 ; x 1 = 1.42 ; x 2 = 3 z_2=327;x_1=1.42;x_2=3 z2=327;x1=1.42;x2=3 | z 1 = 308 ; x 1 = 5.44 ; x 2 = 1 z_1=308;x_1=5.44;x_2=1 z1=308;x1=5.44;x2=1 | 无解 |
- 利用上述结果重新更新界，有上界： z ‾ = 340 \overline z=340 z=340，下界： z ‾ = 340 \underline z=340 z=340，因此得到的最优解就是 B 3 B_3 B3的最优解。
值得注意的是，分支定界法是整数规划命题的精确解法。上述就是整个分支定界的操作流程，重点就是分支+定界，不断迭代去更新界。
割平面法
与分支定界相比的相同点：将整数规划转化为线性规划去做
思路： 先不考虑整数条件，求解对应的线性优化命题，得到最优解，如果存在不满足整数解的变量，则增加切割方程以去除非整数解，在原有的可行域中切割掉一部分。
核心： 寻找切割方程
方法： Gomory割平面法
e.g.
m a x z = x 1 + x 2 s . t . − x 1 + x 2 ≤ 1 3 x 1 + 1 x 2 ≤ 4 x 1 , x 2 ≥ 0 x 1 , x 2 整 数 \begin{aligned} &max&z = x_1 +x_2\\ &s.t. &-x_1 +x_2 \leq1\\ & &3x_1 +1x_2 \leq4\\ & &x_1,x_2 \geq0\\ & &x_1,x_2 整数\\ \end{aligned} maxs.t.z=x1+x2−x1+x2≤13x1+1x2≤4x1,x2≥0x1,x2整数
- 通过单纯形法求解原有原问题，最终得到如下最优结果下的单纯形表。
| 基变量 | b | x 1 x_1 x1 | x 2 x_2 x2 | x 3 x_3 x3 | x 4 x_4 x4 |
|---|---|---|---|---|---|
| x 1 x_1 x1 | 3/4 | 1 | 0 | -1/4 | 1/4 |
| x 2 x_2 x2 | 7/4 | 0 | 1 | 3/4 | 1/4 |
-
对最终的单纯形表进行处理，得到如下的对应式：
x 1 − 1 / 4 x 3 + 1 / 4 x 4 = 3 / 4 x 2 + 3 / 4 x 3 + 1 / 4 x 4 = 7 / 4 x_1-1/4x_3+1/4x_4=3/4\\ x_2+3/4x_3+1/4x_4=7/4 x1−1/4x3+1/4x4=3/4x2+3/4x3+1/4x4=7/4
对上述等式进行分解，分解成整数和非负真分数之和
x 1 + ( − 1 + 3 / 4 ) x 3 + 1 / 4 x 4 = 3 / 4 x 2 + 3 / 4 x 3 + 1 / 4 x 4 = 1 + 3 / 4 x_1+(-1+3/4)x_3+1/4x_4=3/4\\ x_2+3/4x_3+1/4x_4=1+3/4 x1+(−1+3/4)x3+1/4x4=3/4x2+3/4x3+1/4x4=1+3/4
进而将整数部分与分数部分分开，移到等式的左右两边，得到：
x 1 − x 3 = 3 / 4 − 3 / 4 x 3 − 1 / 4 x 4 x 2 − 1 = 3 / 4 − 3 / 4 x 3 − 1 / 4 x 4 x_1-x_3=3/4-3/4x_3-1/4x_4\\ x_2-1=3/4-3/4x_3-1/4x_4 x1−x3=3/4−3/4x3−1/4x4x2−1=3/4−3/4x3−1/4x4 -
观察上述式子可以发现，等式左边必定是整数，那么右边必定也是整数，由于变量的要求均大于等于0，因此右边能够取到的最大整数就是0，一昵称可以得到如下的切割方程：
3 / 4 − 3 / 4 x 3 − 1 / 4 x 4 ≤ 0 3/4-3/4x_3-1/4x_4\leq0 3/4−3/4x3−1/4x4≤0
将该方程作为约束条件添加到原命题中进行重新求解，不断重复寻找切割方程直到找到满足整数条件的最优解。
后续还会介绍到相关的整数规划解法，例如列生成、以及组合的Branch and cut、Branch and price 以及benders decomposition等方法，同时也会简答说一下相关的改进以及相关求解器