上一章简要介绍了线性规划，这一章再继续介绍线性规划中的一个特殊问题，整数线性规划。

在标准线性规划的问题中我们将\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 算法：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）来方便解。

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数量是没有上界的，当计算量十分巨大无法完全计算时，我们也没有一个次优的解。

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。