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 Google Scholar Google Scholar Articles by Naddef, D. Articles by Rinaldi, G. Search for Related Content

The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation

Laboratoire G-SCOP, Institut National Polytechnique de Grenoble, 46, avenue Félix-Viallet, 38031 Grenoble, France
Istituto di Analisi dei Sistemi ed Informatica "Antonio Ruberti" del CNR, viale Manzoni 30, 00185 Roma, Italy
denis.naddef{at}g-scop.inpg.fr, http://www.g-scop.inpg.fr/naddefd/
rinaldi{at}iasi.cnr.it, http://www.iasi.cnr.it/iasi/personnel/rinaldi.html

The path, the wheelbarrow, and the bicycle inequalities have been shown by Cornuéjols, Fonlupt, and Naddef to be facet-defining for the graphical relaxation of STSP(n), the polytope of the symmetric traveling salesman problem on an n-node complete graph. We show that these inequalities, and some generalizations of them, define facets also for STSP(n). In conclusion, we characterize a large family of facet-defining inequalities for STSP(n) that include, as special cases, most of the inequalities currently known to have this property as the comb, the clique tree, and the chain inequalities. Most of the results given here come from a strong relationship of STSP(n) with its graphical relaxation that we have pointed out in another paper, where the basic proof techniques are also described.

Key Words: traveling salesman problem; Hamiltonian cycle; polyhedron; facet; linear inequality
History: Received: October 29, 2004; revision received: July 25, 2006;