This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Grötschel, M. Articles by Pulleyblank, W. R. Search for Related Content

Clique Tree Inequalities and the Symmetric Travelling Salesman Problem

Mathematisches Institut, Universität Augsburg, Augsburg, Federal Republic of Germany
Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario, Canada

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.), Grötschel (Grötschel, 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.

Key Words: traveling salesman problem; cutting planes; facets; integer polytopes

This article has been cited by other articles:

				D. Naddef and G. Rinaldi The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation Mathematics of Operations Research, February 1, 2007; 32(1): 233 - 256. [Abstract] [PDF]

				D. Naddef and Y. Pochet The Symmetric Traveling Salesman Polytope Revisited Mathematics of Operations Research, November 1, 2001; 26(4): 700 - 722. [Abstract] [PDF]

				E. L. Johnson, G. L. Nemhauser, and M. W.P. Savelsbergh Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition INFORMS Journal on Computing, January 1, 2000; 12(1): 2 - 23. [Abstract] [PDF]