7.3 整数规划的分支定界法

分支定界算法植根于TSP研究，诞生后不久就成功打入了一般的整数规划领域。整数规划分支定界法的研究先驱是Ailsa Land和Alison Doig，她们来自伦敦政治经济学院。¹

_{1. Land, A. H., A. G. Doig. 1960. Econometrica 28, 497–520.}

图7-4　Ailsa Land，英国班夫郡，摄于1977年

在2010年出版的回忆录里，她们两人讨论了当年提出的算法程序。²

_{2. Land, A. H., A. G. Doig. 2010. In: Jünger et al., eds. 50 Years of Integer Programming 1958–2008. Springer, Berlin. 387–430.}

起初，我们并没有把该方法看成是“分支定界法”，而是考虑了它的“几何学”解释，即对线性规划约束条件定义的凸包可行域进行探索。我们不太清楚，此前文献中是否已经提到过“分支定界法”，不过就算前人提到过，我们也并没有想到使用这个名称。还记得Steven Vadja说他见过一些通过“Lawndwa”解决整数线性规划问题的法国人。我们意识到所谓“Lawndwa”是“Land-Doig”的法语读音，由此认为法国人也并不知道“分支定界”这种说法。

Land-Doig的基本方法主导了整数规划计算的实际应用，在一定意义上，这是基于割平面的Gomory算法未曾取得的成就。直到20世纪90年代中期以后，分支切割法才成为整数规划商业软件的主力，标志着两大竞争对手终于开始携手合作。