This Article Full Text (PDF) References 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 Naddef, D. Articles by Pochet, Y. Search for Related Content

The Symmetric Traveling Salesman Polytope Revisited

Laboratoire d'Informatique et Distribution, Institut National Polytechnique de Grenoble, Antenne de Montbonnot; ZIRST, 51 avenue Jean Kuntzmann, 38330 Montbonnot Saint Martin, France
CORE, Center for Operations Research and Econometrics, Voie du Roman Pays 34, B-1348 Louvain-la-Neuve, Belgium
denis.naddef{at}imag.fr
ypochet{at}core.ucl.ac.be

In this paper we present a tour of the symmetric traveling salesman polytope, focusing on inequalities that can be defined on sets of nodes. Most widely known inequalities are of this type. Many papers have appeared that give increasingly complex valid inequalities for this polytope, but little intuition on why these inequalities are valid has been given.

To help in understanding these inequalities, we develop an intuition into their validity by giving a unifying way of defining them through a sequential lifting procedure. This procedure is based on lifting the slack variables associated with subtour elimination inequalities defined on sets of nodes (called teeth). We apply this procedure to some known classes of valid inequalities for the traveling salesman polytope (TSP) respectively comb, brush, star, path, and bipartition inequalities, where the lifting coefficients are sequence independent. For comb, star, and bipartition inequalities, we provide new and noninductive proofs of validity directly inspired by this lifting procedure. We also give an example where a facet-defining inequality is derived from the lifting procedure, but where the lifting coefficients are sequence dependent. We finally study the ladder inequalities and show that they can be generated by an extension of the general procedure, where the lifted variables are different from the slack variables of subtour elimination inequalities.

Key Words: Traveling salesman problem; traveling salesman polytope; valid inequality; facet
History: Received: February 2, 1999; revision received: March 13, 2001;

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]