6.5 整数规划的割平面

天堂谈得差不多了，下面脚踏实地，考虑一下整数规划问题。成功的整数规划方法都扎根于TSP研究，割平面法也不例外。它绝对是新型整数规划解题程序里最重要的工具。无论是子回路约束条件，还是梳子不等式，抑或团树不等式，都是专门用来解决TSP的；但是，通过割平面逐步改进线性规划松弛解的整体方法却是通用的，它同样可以用来解决一般的整数规划问题。

Ralph Gomory是第一个认真研究整数规划割平面的人。后来，他几度升职，在IBM公司担任高级副总裁，负责科技部门，又在美国斯隆基金会（Alfred P. Sloan Foundation）担任主席。20世纪50年代中期，Gomory还在普林斯顿大学数学系，只是一名默默无闻的博士后学生。当时，他在研究如何从线性规划问题中分离出整数值的解。他学习过古典数学，因此求解时力图使用丢番图分析理论，即不定方程理论。丢番图分析（Diophantine analysis）就是对线性方程（组）整数解的研究。对线性规划模型里用到的线性不等式进行推广似乎会有效果，但是没日没夜地奋战了整整一周之后，所有的结果依然不过是一堆只做出来一半的题目。¹

^{1. Gomory, R. E. 2010. In: Jünger et al., eds. 50 Years of Integer Programming 1958–2008. Springer, Berlin. 387–430.}

第八天傍晚，我已经无计可施了。可是我依然相信，对于一切给定具体系数取值的不定方程题目，如果有必要给出整数解，那么我肯定总有办法给出来的。当时，我暗暗问自己：假如你真的必须解决某道具体的题目，必须想方设法求出答案，那么你第一步会做什么？我的第一反应就是，第一步会解决相应的线性规划（最大值）题目，如果答案解出来是7.14，那么我至少知道整数解最大不可能超过7。我心里刚想到这个显然的结论，马上感觉左脚两只脚趾突然发麻，当下我就意识到，这是个非同寻常的结论，在经典丢番图分析里绝对没出现过。

上面的思想是说，如果知道一道线性规划题目的所有解都满足不等式3x+2y≤7.14，那么我们就知道所有整数解也都满足3x+2y≤7。因此，所有与线性规划可行域相切的半平面都可以再推进一点点，而不会“切割掉”任何整数解。²

^{2. 20世纪70年代初期，对右侧向下取整以加强线性不等式的思想由Vašek Chvátal发展为精细的理论。}

Gomory根据这个结论，研究出了一种解决纯整数规划问题的算法。所谓纯整数规划问题是指所有变量都必须取整数值的线性规划问题。Gomory割平面法借鉴了单纯形算法的形式，每当字典给一个变量赋非整数值时，就推导出一个割平面。他的论文篇幅虽然短小，却在几年内彻底颠覆了整数规划领域的研究局面。可惜，后来计算机速度提高，能够解决大型题目了，Gomory割平面法在实际应用上表现不佳的劣势也变得一览无遗。即便如此，这段故事的结局还是很美好：Gomory割平面法中，构造割平面的机制同样出自他之手，而如今的整数规划解题商业软件用到的正是这种机制的变体。