Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
复制标题
DOI：
10.1287/moor.11.4.537
复制
发表时间：
1986-11
期刊：
影响因子：
--
通讯作者：
M. Grötschel;W. Pulleyblank
中科院分区：
文献类型：
--
作者：
M. Grötschel;W. Pulleyblank
线性规划切割平面的方法来解决旅行推销员的问题，最近被证明是非常成功的，参见。Crowder和Padberg Crowder，H. P.，M. W.帕德伯格1980.大规模对称旅行商问题的最优解。管理科学26 495--509.，Grotschel，M. 1980年a。关于对称旅行推销员问题：120个城市问题的解决方案。数学程序设计研究12 61- 77.，Padberg和Hong Padberg，M. W.，S.洪1980.关于对称旅行商问题：计算研究。数学.编程学习. 12 78--107..这种成功的原因之一当然是这样一个事实，即代替普通的切割平面，Gomory切割等，可以使用特定于问题的切割平面，其定义了底层整数规划多面体的面。在本文中，我们将定义一类新的不等式集团树不等式有效的旅行推销员多面体适当地包含了许多已知的类的不平等，如subtour消除约束，2-匹配约束，梳状不等式，我们表明，所有这些新的不平等导致方面的旅行推销员多面体。由于这些新的不等式的一般结构是相当简单的，我们希望它将有可能有效地使用的不平等切割平面程序的旅行推销员问题。
The linear programming cutting plane approach for solving the travelling salesman problem has recently proven to be highly successful, cf. Crowder and Padberg Crowder, H. P., M. W. Padberg. 1980. Solving large-scale symmetric travelling salesman problems to optimality. Management Sci.26 495--509., Grotschel Grotschel, M. 1980a. On the symmetric travelling salesman problem: Solution of a 120 city problem. Math. Programming Stud.12 61--77., Padberg and Hong Padberg, M. W., S. Hong. 1980. On the symmetric travelling salesman problem: A computational study. Math. Programming Stud.12 78--107.. One of the reasons for this success is certainly the fact that instead of ordinary cutting planes Gomory-cuts etc. problem-specific cutting planes could be used which define facets of the underlying integer programming polytopes. In this paper we shall define a new class of inequalities clique tree inequalities valid for the travelling salesman polytope which properly contains many of the known classes of inequalities like subtour elimination constraints, 2-matching constraints, comb inequalities, and we show that all these new inequalities induce facets of the travelling salesman polytope. Since the general structure of these new inequalities is quite simple we hope that it will be possible to use the inequalities efficiently in cutting plane procedures for the travelling salesman problem.