解整数规划 | 彩潭有鲤的札记

type

status

date

slug

summary

为什么会有整数规划？

线性规划问题的最优解可能是分数或小数。整数规划是指变量的取值只能是整数的规划。

这在实际问题中很常见，例如车间人数、设备台数、行驶次数，这些变量显然必须取整数解。

整数规划并不一定是线性规划问题的变量取整限制，对于二次规划、非线性规划问题也有变量取整限制而引出的整数规划。这里所说的整数规划，通常是指整数线性规划。

根据对变量的不同情况，整数规划又可以分为：

完全整数规划，全部变量都要求是整数；

混合整数规划，部分变量要求是整数；

0-1整数规划，变量的取值只能是 0 或 1；

混合0-1规划，部分变量的取值只能是 0 或 1。

0-1整数规划是非常重要也非常特殊的整数规划

四舍五入就能得到整数解吗？

整数规划问题与线性规划问题的区别只是增加了整数约束。这看上去好像只要把线性规划得到的非整数解舍入化整，就可以得到整数解，并不是多么复杂的问题。

但是问题并没有这么简单。化整后的解不仅不一定是最优解，甚至不一定是可行解的——线性规划的最优解，取整后可能就不满足约束条件了。

那么，不要按四舍五入取整，而是向满足约束条件的方向取整，是不是就可以呢？这是很好的想法，通常这样可以获得可行解，但却不一定是最优解了。

因此，整数规划问题比线性规划复杂的多，以至于至今还没有通用的多项式解法，也就是说算法复杂度与问题规模成指数关系（NP问题）。还没有意识到与问题规模指数关系意味着什么吗？就是那个在象棋棋盘上放麦子，每格比前一格加倍的故事。问题区别一点点，难度却相差千万里。

整数规划的求解方法

分支定界法（Branch and bound）

分支定界法的基本思想是把原问题（整数规划问题）转换为一个个线性规划问题来处理，并在求解这些线性规划问题的过程中不断追踪原问题的上界（最优可行解）和下界（最优线性松弛解）。

分支定界法把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标上界，称为定界。每次分枝后，对于超出已知可行解集目标值的那些子集不再进一步分枝，就可以删减很多子集，这称为剪枝。设有最大化的整数规划问题 A，先解与之相应的线性规划问题 B，若 B 的最优解不符合 A 的整数条件，则 B 的最优目标函数必是 A 的最优目标函数 z 的上界，记为，而 A 的任意可行解的目标函数值将是 z 的一个下界。分支定界法就是将 B 的可行域分成子区域（分支）的方法，逐步减小和增大，最终求到 z*。

分支定界法是一个迭代算法，随着迭代过程不断更新上界和下界，直到上界和下界非常接近时结束。通常设置，就可把当前的最优可行解近似为问题的全局最优解了。因此，分支定界法的“收敛” 不是分析意义上的而是算法意义上的，优化结果是近似解而不是精确解。

分支定界法不用区分完全整数规划与混合整数规划，算法便于实现，但计算量比较大。

割平面法（Cutting plane）

割平面法的基本思路是先求解普通线性规划问题的最优解，再对非整数解添加约束条件使可行域缩小，如此反复求解添加了约束条件的普通线性规划问题，直到得到整数解。

也就是说，先不考虑整数约束条件，直接求解松弛问题的最优解，如果满足整数条件就结束了，如果不满足整数条件，就在此非整数解的基础上增加新的约束条件重新求解。这个新增加的约束条件称为割平面，对松弛问题的可行域割一刀，割去松弛问题的部分非整数解。经过有限次的反复切割，必定可在缩小的可行域的一个整数极点上达到整数规划问题的最优解。

割平面法的计算量比较小，但对问题的结构及求解的要求较高，算法比较复杂。