整数规划

整数规划要求一部分或全部决策变量只能取整数。订购三分之一台机器、让同一个人在两个岗位各占半个名额，通常不是可以执行的方案；这种“不可分”必须写进模型，而不能在求解以后随意四舍五入。

一个有预算上限的选择

有两项独立项目，A 花费 4 单位预算、带来 7 单位收益，B 花费 3、带来 5；预算只有 5。以 $x,y\in \{0,1\}$ 表示是否分别选择 A、B，模型为 $$max7x+5y,4x+3y\le 5,x,y\in \{0,1\}.$$ 四种组合中，两个都选会花 7 而不可行；只选 A、只选 B、都不选的收益分别是 7、5、0。因此整数最优值为 7。

若暂时把 $x,y$ 放宽到 $0\le x,y\le 1$，得到线性松弛。A 的单位预算收益为 $7/4$，高于 B 的 $5/3$。若松弛解同时有 $x<1$ 与 $y>0$，从 B 的用量减少 $\delta$，把省下的预算用于把 A 增加 $3\delta /4$，预算不变而收益增加 $7(3\delta /4)-5\delta =\delta /4>0$。所以最优解必有 $x=1$ 或 $y=0$；后者最多收益 7，前者把剩余预算用于 B，得到 $y=1/3$、松弛最优值 $7+5/3=26/3$。这个值高于可执行的 7，它是整数最大化问题的上界，并不是完成项目的真实收益。把 $y=1/3$ 四舍五入到 0，碰巧得到本例最优解；若取整规则或约束改变，舍入结果可能违反预算。0-1背包问题就是这一类模型的重要特例。

舍入失效可以在更小的模型中直接看到。若 $x,y\in \{0,1\}$ 且 $2x+2y\le 3$，连续松弛允许 $(x,y)=(3/4,3/4)$；分别四舍五入到 1 后，左边变成 4，超过容量 3。反过来，若无条件都向下取整，虽然保住这个例子的可行性，却可能损失很多目标值。因此对松弛解必须另行设计并验证取整规则。

用上下界证明最优

本例可以在 $y$ 上分支。分支 $y=0$ 时，$x\le 1$，收益最多 7，并且 $(1,0)$ 达到它。分支 $y=1$ 时，预算给出 $4x\le 2$；即使继续允许 $x$ 取分数，这一分支的收益也最多为 $5+7/2=17/2$。这个上界仍超过 7，所以还不能据此剪枝；继续利用 $x\in \{0,1\}$，可知 $x=0$，收益只有 5。两个分支的最大收益分别为 7、5，故全局最优是选 A。较大的问题采用分支定界所用的“松弛上界、已有整数方案下界、再拆分”思路，本页算例只有一个分支层。

整数要求怎样改变模型

若 $x$ 表示购买设备的台数，可写 $x\in {\mathbb{Z}}_{\ge 0}$；若只表示“建或不建”，则写二元变量 $z\in \{0,1\}$。连续产量 $q$ 与开机变量 $z$ 可以用 $0\le q\le Uz$ 联系：不开机时 $z=0$ 迫使产量为零。这里 $U$ 必须是经过核实的产能上界；随意把它设得极大，会使线性松弛过松，也会恶化数值求解。

只有整数变量时称纯整数规划；若同时有整数与连续变量，称混合整数规划。线性目标和线性约束构成整数线性规划；出现非线性关系时须另作区分。整数限制使可行域成为离散点集，所以凸优化中的“局部最优即全局最优”不能直接移用。针对不同结构，可以用分支定界、割平面或动态规划；计算结果需要同时核对可行性与最优性界。

参考资料

• MIT 15.053《Integer programming techniques 1》，介绍整数规划的分支定界。
• MIT 15.053 课程讲义目录，含整数规划建模、松弛和割平面资料。