6.4 Edmonds的“天堂之光”

诚然，不等式质量越高，给出的路线长度下界就越准确，相应的计算机程序运行速度也就越快。可是，从不等式切入的这条研究路线最终能否通向百万美元大奖的领奖台呢？我们有一个先例可供参考，那就是Jack Edmonds对完美匹配问题给出的惊天妙解¹。

^{1. Edmonds, J. 1965. Canadian J. Math. 17, 449–467.}

图的完美匹配就是将顶点两两配对的一组边。换言之，每个顶点都恰好是完美匹配中的唯一一条边的端点。如果把代价值赋给图的各边，则完美匹配问题就是寻找完美匹配，使其中的各边代价之和最小。这道题和TSP一样，很难发现高效解法。

既然我们不知道怎样才能求解这道最优化问题，最好请线性规划对偶性出场。事实上，完美匹配满足一种形式的度约束条件，具体说来，每个顶点的度（与顶点相连的边的总数）都应该是1。这个切入点不错，我们还需要合适的割平面。Edmonds提供了所需的割平面。他提出的带花树开花不等式（blossom inequality）表明，顶点数目为奇数的图不可能存在完美匹配。因此，图中任取一个顶点数目为奇数的簇，完美匹配中必须至少有一条边连接该顶点簇与图的其余部分。相应的线性不等式与子回路消去不等式左端形式相同，但前者只要求取值至少为1，而后者要求至少为2。

Edmonds一次性把所有开花不等式都添加到线性规划模型之中，每个奇数集合S都对应一个不等式，也就是一个割平面。然后他证明了，得到的多面体确实是图的完美匹配的凸包。利用这种描述，他得以直接使用线性规划对偶性，构造出一个多项式时间算法，无需逐步选择割平面就能计算得到最小代价完美匹配。这个结果非同寻常，他自己总结道：“这有一个好算法，这有一个已经攻克了的整数规划问题。要知道，这是一场布道，一场货真价实的布道。这有一个已经攻克了的整数规划问题。这是我第一次看到天堂之光。”²

^{2. Edmonds (1991).}

他的结果能不能用来解决TSP呢？1964年，Edmonds探讨得出，TSP多面体顶点虽然数目庞大，但是有统一的简单描述，因此小平面可能也有简单描述。他写道：“至少应该对此抱有希望，因为找到相当出色的旅行商问题算法无疑等价于找到这样的简单描述。”³他的断言的确大胆，却准确洞见了大奖的方向。事实上，1979年，Khachiyan的线性规划算法登上了《纽约时报》的封面，而它恰恰具有一个有趣的性质：无需列出线性规划问题的显式约束条件，只要有可用的分离程序，就可以执行这个算法。⁴因此，Khachiyan算法只需服从几个技术条件，就可以用来证明：根据好的分离算法可以得到好的最优化算法；反之亦然，根据好的最优化算法也可以得到好的分离算法。这个数学结论非常深刻，最完整的形式于20世纪80年代获得证明，证明者是Martin Grötschel、László Lovász和Alexander Schrijver。⁵

^{3. Gomory (1966).}

^{4. Khachiyan算法基于通用算法“椭球法”（ellipsoid method），后者由David Yudin和Arkadi Nemirovski发明。}

^{5. Grötschel, M., L. Lovász, A. Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization, 2nd edition. Springer, Berlin, Germany.}

由此推知，要想解决TSP，必须给出路线凸包的描述，还要配备多项式时间的分离算法。漂亮的推论！从务实的算法工程角度，TSP需要用到更快、更好的分离算法，而这种方法同样也与克雷数学研究所的百万美元大奖紧密联系在一起。如果能够实现就太棒了！我们将再次目睹天堂之光！