上一章简要介绍了线性规划，这一章再继续介绍线性规划中的一个特殊问题，整数线性规划。（为了突出本文重点，添加了解法实例）

Formulation

在标准线性规划的问题中我们将\boldsymbol x限制为整数，就得到了标准的整数线性规划问题，就是ILP (Integer-linear-programming problem)：
\begin{aligned}
\min\quad &\boldsymbol c^\mathsf T\boldsymbol x\\
\text{s.t.}\quad&A\boldsymbol x=\boldsymbol b,\\
&\boldsymbol x\geqslant0,\\
&\boldsymbol x\in\mathbb Z^n.
\end{aligned}
如果只是一部分变量限制为整数，那么就得到了混合整数线性规划问题，就是MILP (Mixed-integer-linear programming problem)：
\begin{aligned}
\min\quad &\boldsymbol c^\mathsf T\boldsymbol x+\boldsymbol d^\mathsf T\boldsymbol v\\
\text{s.t.}\quad&A _ 1\boldsymbol x+A _ 2\boldsymbol v=\boldsymbol b,\\
&\boldsymbol x\geqslant0,\, \boldsymbol v\geqslant0,\\
&\boldsymbol x\in\mathbb Z^n.
\end{aligned}
整数线性规划可以用来建模一系列的问题。我们甚至能常见一些布尔变量就能强力表示的例子。ILP这种强大的“表示能力”不容小觑，因而有必要对其略作了解，列出一章。

为作示意，考虑一个分段线性函数的例子。设这个函数的折点为(a _ i,f(a _ i))\, (1\leqslant i\leqslant k)，那么x\in[a _ 1,a _ k]可表示为x=\sum\lambda _ ia _ i，其中\lambda _ i是权重：非负且和为1；而对于f(x)，可以对照下述的混合整数规划问题：
\begin{aligned}
\min\quad&\sum\lambda _ if(a _ i)\\
\text{s.t.}\quad&\sum\lambda _ i=1,\quad \lambda _ i\geqslant0,\\
&\lambda _ i\leqslant y _ {i-1}+y _ i,\, 1\leqslant i\leqslant k-1,\, y _ 0=y _ {k}=0,\\
&\sum y _ i=1,\\
&y _ i\in\{0,1\}.
\end{aligned}

引入二元变量y _ i，富有技巧性地表示了f(x)，可以自行验证。除了这个例子之外，这里不再继续介绍ILP的建模问题，下面我们关注其解法。

显然对整数进行穷举不是一个好的方案，一般的做法是先解对应的可以取实值的线性规划问题，然后在此基础上再得到对应的整数线性规划的解。下面列举两个应用广泛的方法：branch-and-bound法，和cutting plane法。

Branch-and-bound

将问题的可行域记作F，我们考虑将F进行划分得到F _ i，然后在这些小的可行域上求解。求解各个小问题可能并不能很好解决问题，所以我们可能会在小的可行域上进一步的划分更小的可行域，这就是这个方法的branching部分，我们得到的是一系列子问题构成的树。

或许在各个子问题里我们很难优化到函数最小值，但我们也许可以轻松地得到一个下界。例如，在整数线性规划里要求函数的最小值，那么这个最值肯定比\boldsymbol x自由取值时的最值要大，也就是说我们可以通过解其对应的LP得到这个ILP的下界。

与此同时，ILP最值的上界也是可以轻易得到的。例如求解一个子问题，其最优解对应的函数值就是一个上界。我们求解大问题的关键就是，如果某一个子问题它的最优解函数值都比这个上界大，那就没有必要继续解这个子问题了。

Branch and bound 算法：0. 初始化U=+\infty；1. 选择一个active的子问题F_i；2. 如果这个子问题不可行，删除之；否则，计算这个子问题的一个下界；3. 如果这个下界比U大，就删除这个子问题；4. 如果比U小，则求解这个子问题，或者进一步划分更细的子问题。

将这个算法应用到ILP，我们可以先解对应的LP，如果存在非整数的分量x_i^\ast，那么我们按x_i\leqslant\lfloor x_i^\ast\rfloor以及x_i\geqslant\lceil x_i^\ast\rceil划分两个子问题。由于两个子问题仅比原来的问题多了一条限制，我们解这两个子问题的LP时可以通过dual simplex（始于\boldsymbol x^\ast）来方便解。

实例：考虑如下整数线性规划问题：
\begin{aligned}\min\quad&x_1-2x_2\\\text{s.t.}\quad& -4x_1+6x_2\leqslant 9,\\&x_1+x_2\leqslant 4,\\&x_1,x_2\geqslant0,\, x_1,x_2\in\mathbb Z.\\\end{aligned}
先变为
\begin{aligned}\min\quad&x_1-2x_2\\\text{s.t.}\quad& -4x_1+6x_2+x_3= 9,\\&x_1+x_2+x_4= 4,\\&x_1,\dots,x_4\geqslant0,\, x_1,\dots,x_4\in\mathbb Z.\\\end{aligned}求解对应的LP，得到其simplex tableau如下

	x_1	x_2	x_3	x_4	Solution
z	0	0	-3/10	-1/5	-7/2
x_2	0	1	\phantom{-}1/10	\phantom{-}2/5	\phantom{-}5/2
x_1	1	0	-1/10	\phantom{-}3/5	\phantom{-}3/2

（注记：以防带来误解，这里表示的是z-\frac3 {10}x_3-\frac15x_4=-\frac72、x_2+\frac1{10}x_3+\frac25x_4=\frac52以及x_1-\frac1{10}x_3+\frac35x_4=\frac32，然后要令x_3=x_4=0）

对应的LP的最优解是\boldsymbol x^1=(3/2,5/2)，最小值-7/2。我们划分更细的子问题：一个是x_2\leqslant 2，另一个是x_2\geqslant 3。

对于x_2\geqslant3的情况，可以验证对偶最大为+\infty，因此原问题不可行。当然也可以直接看出来：x_1+x_2+x_4=4表明x_1至多为1，而-4x_1+6x_2+x_3=9的左边至少是-4+6\times3>9，矛盾，故x_2\geqslant3时不可行。

对于x_2\leqslant2的情况，添加限制：x_2+x_5=2，x_5\geqslant0，求解得到

	x_1	x_2	x_3	x_4	x_5	Solution
z	0	0	-1/4	\phantom{-}0	-1/2	-13/4
x_2	0	1	\phantom{-1/}0	\phantom{-}0	\phantom{-1/}1	\phantom{-13/}2
x_1	1	0	-1/4	\phantom{-}0	\phantom{-}3/2	\phantom{-1}3/4
x_4	0	0	\phantom{-}1/4	\phantom{-}1	-5/2	\phantom{-1}5/4

有\boldsymbol x^2=(3/4,2)及最小值-13/4。我们进一步划分子问题：一个是x_1\geqslant1，另一个是x_1\leqslant0。

对于x_1\geqslant1的情况，添加限制x_1-x_6=1，x_6\geqslant0，求解得到（compact的）

	x_5	x_6	Solution
z	-2	-1	-3
x_2	\phantom{-}1	\phantom{-}0	\phantom{-}2
x_1	\phantom{-}0	-1	\phantom{-}1
x_4	-1	\phantom{-}1	\phantom{-}1
x_3	-6	-4	\phantom{-}1

有\boldsymbol x^3=(1,2)及最小值-3。至此我们得到了一个整数解，可以更新U=-3。

再来看x_1\leqslant0的情况，求解得\boldsymbol x^4=(0,3/2)，最小值-3，并未小于U，因此这个子问题可以不作考虑了。

至此已经考虑完所有的子问题，综合可知最优解是\boldsymbol x^3=(1,2)，最小值是-3。

Cutting plane

ILP

这个方法是通过求解一系列LP来解这个ILP。思想是，原LP的最优解\boldsymbol x^\ast如果不是整数解，那么就添加限制，使得原ILP的所有整数解仍可行，但\boldsymbol x^\ast就不再可行。

Cutting plane 算法：1. 解LP得到最优解\boldsymbol x^\ast；2. 如果是整数解，返回这个解；3. 否则，添加一个线性不等式使得所有整数解可行，但\boldsymbol x^\ast不可行，回到步骤1.

最先提出的能够保证有限步后终止的整数规划算法是Gomory在1958年提出的cutting plane算法，这个算法用到了一些最优simplex tableau的信息。假设我们解LP得到了最优解\boldsymbol x^\ast的simplex tableau，不妨设前m个变量是基变量。考察某一行最后一列的数不是整数（设为第r行）所对应的方程，x _ r+\sum _ {j=m+1}^nc _ {ri}x _ i=x _ r^\ast，由此可知x _ r+\sum _ {j=m+1}^n\lfloor c _ {ri}\rfloor x _ i\leqslant x _ r^\ast，进而
x _ r+\sum _ {j=m+1}^n\lfloor c _ {ri}\rfloor x _ i\leqslant \lfloor x _ r^\ast\rfloor.
这就是我们需要的额外限制，即原ILP的所有整数解都满足但\boldsymbol x^\ast不满足的限制，这是因为对于\boldsymbol x^\ast，左边由于x^\ast _ {m+1}=\dots=x^\ast _ n=0值为x _ r^\ast，按前面的选择这是一个非整数，所以x^\ast _ r>\lfloor x _ r^\ast\rfloor，所以\boldsymbol x^\ast不满足这条额外限制。

可以证明，在恰当的逐步添加限制、使用dual simplex和anticyling规则之下，我们将得到一个可以解决一般的整数规划问题的有限步终止的算法。

对x _ r+\sum _ {j=m+1}^n\lfloor c _ {ri}\rfloor x _ i\leqslant \lfloor x _ r^\ast\rfloor也可以做进一步分析。由于x _ r+\sum _ {j=m+1}^nc _ {ri}x _ i=x _ r^\ast，我们得知\sum _ {j=m+1}^n\{c _ {ri}\}x _ i\geqslant\{x _ r^\ast\}，这里\{\cdot\}表示一个数的小数部分。令S=\sum _ {j=m+1}^n\{c _ {ri}\}x _ i-\{x _ r^\ast\}，那么S\geqslant0且S是个整数（当\boldsymbol x也是整数解时）：S=\sum _ {j=m+1}^nc _ {ri}x _ i-x^\ast _ r-\sum _ {j=m+1}^n\lfloor c _ {ri}\rfloor x _ i+\lfloor x^\ast _ r\rfloor=-x _ r-\sum _ {j=m+1}^n\lfloor c _ {ri}\rfloor x _ i+\lfloor x^\ast _ r\rfloor。

因此可以添加的限制也可以是
S=\sum _ {j=m+1}^n\{c _ {ri}\}x _ i-\{x _ r^\ast\},\, S\geqslant0,\, S\in\mathbb Z.
这个算法的缺陷在于：在计算机上实现时，浮点数误差可能会带来严重问题，尤其是区分整数和非整数；另一方面，添加的cut数量是没有上界的，当计算量十分巨大无法完全计算时，我们也没有一个次优的解。

实例：仍考虑上面的ILP问题：
\begin{aligned}\min\quad&x_1-2x_2\\\text{s.t.}\quad& -4x_1+6x_2+x_3= 9,\\&x_1+x_2+x_4= 4,\\&x_1,\dots,x_4\geqslant0,\, x_1,\dots,x_4\in\mathbb Z.\\\end{aligned}求解对应的LP，得到其simplex tableau如下

	x_1	x_2	x_3	x_4	Solution
z	0	0	-3/10	-1/5	-7/2
x_2	0	1	\phantom{-}1/10	\phantom{-}2/5	\phantom{-}5/2
x_1	1	0	-1/10	\phantom{-}3/5	\phantom{-}3/2

（注记：以防带来误解，这里表示的是z-\frac3 {10}x_3-\frac15x_4=-\frac72、x_2+\frac1{10}x_3+\frac25x_4=\frac52以及x_1-\frac1{10}x_3+\frac35x_4=\frac32，然后要令x_3=x_4=0）

对应的LP的最优解是\boldsymbol x=(3/2,5/2)。

对tableau中的一条方程应用cutting plane：
x_2+\frac1{10}x_3+\frac25x_4=\frac52\implies x_2\leqslant 2.因此在LP里添加限制x_2+x_5=2，x_5\geqslant0。求解得到

	x_1	x_2	x_3	x_4	x_5	Solution
z	0	0	-1/4	\phantom{-}0	-1/2	-13/4
x_2	0	1	\phantom{-1/}0	\phantom{-}0	\phantom{-1/}1	\phantom{-13/}2
x_1	1	0	-1/4	\phantom{-}0	\phantom{-}3/2	\phantom{-1}3/4
x_4	0	0	\phantom{-}1/4	\phantom{-}1	-5/2	\phantom{-1}5/4

有\boldsymbol x=(3/4,2)。对tableau中的方程继续应用cutting plane：
x_1-\frac14x_3+\frac32x_5=\frac34\implies x_1-x_3+x_5\leqslant0.额外限制是x_1-x_3+x_5+x_6=0，x_6\geqslant0。求解得到\boldsymbol x=(1,2)及最小值-3。

MILP的mixed cut

这个与ILP略有不同，因为有的变量不再限制是整数。我们继续考察MILP可行解的必要条件。

对I=\{m+1,\dots,n\}，我们进一步根据c的正负对其划分：J^+=\{i\in I\mid c _ {ri}\geqslant0\}及J^-=\{i\in I\mid c _ {ri}<0\};回到x _ r+\sum _ {j=m+1}^nc _ {ri}x _ i=x _ r^\ast，对于整数x _ r，只能x _ r\leqslant\lfloor x _ r^\ast\rfloor或者x _ r\geqslant\lfloor x _ r^\ast\rfloor+1，所以\{x _ r^*\}\leqslant\sum _ {i=m+1}^nc _ {ri}x _ i

或者\{x _ r^\ast\}-1\geqslant\sum _ {i=m+1}^nc _ {ri}x _ i，进而\{x _ r^*\}\leqslant\sum _ {i\in J^+}c _ {ri}x _ i或\{x _ r^\ast\}-1\geqslant\sum _ {i\in J^-}c _ {ri}x _ i，后者改写为\{x _ r^\ast\}\leqslant\frac{\{x _ r^\ast\}}{\{x _ r^\ast\}-1}\sum _ {i\in J^-}c _ {ri}x _ i，于是可以考虑如下限制：
S-\Big(\sum _ {i\in J^+}c _ {ri}x _ i+\frac{\{x _ r^\ast\}}{\{x _ r^\ast\}-1}\sum _ {i\in J^-}c _ {ri}x _ i\Big)=-\{x _ r^\ast\}.

其中S\geqslant0是slack变量。

这个限制\boldsymbol x^\ast不满足，因为非整数x必有\lfloor x\rfloor<x<\lfloor x\rfloor+1。