第6章 割平面法

首先，Dantzig、Fulkerson和Johnson用绳子在实体模型上得到一个解（实际上也是最优解），接下来，他们依然必须面对无数种可能的切割方式。

——Alan Hoffman和Philip Wolfe，1985年¹

^{1. Hoffman和Wolfe (1985).}

与旅行商问题相关的线性规划的松弛问题极为复杂，因为单纯形算法无法解决有几十亿约束条件的大型题目。幸运的是，Dantzig、Fulkerson和Johnson面对这种复杂性，提出了一种巧妙的处理方案。他们的方法称为割平面法。割平面法的目标不是一举解决整个线性规划问题，而是以“随用随取”为原则，只在必要的时候才产生相应的TSP不等式，从而逐步计算线性规划的边界。从此，游戏局面改变了，而且这种改变并不局限在旅行商的世界里。