article

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

Authors:

Giovanni RinaldiAuthors Info & Claims

Mathematics of Operations Research, Volume 32, Issue 1

Pages 233 - 256

https://doi.org/10.1287/moor.1060.0244

Published: 01 February 2007 Publication History

Abstract

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.

References

[1]

Balas, E. and Fischetti, M., "On the monotonization of polyhedra," Math. Programming, v77, pp. 59-84, 1997.

Digital Library

[2]

Christof, T. and Reinelt, G., "Combinatorial optimization and small polytopes," TOP, v4, pp. 1-53, 1996.

[3]

Chvátal, V., "Edmonds polytopes and weakly Hamiltonian graphs," Math. Programming, v5, pp. 29-40, 1973.

Digital Library

[4]

Clochard, J. M., Naddef, D., Rinaldi, G. and Wolsey, L. A., "Using path inequalities in a branch and cut code for the symmetric traveling salesman problem," Proc. 3rd Math. Programming Conf. Integer Programming Combin. Optim., CORE, Louvain-la-Neuve, Belgium, pp. 291-311, 1993.

[5]

Cornuéjols, G., Fonlupt, J. and Naddef, D., "The traveling salesman problem on a graph and some related integer polyhedra," Math. Programming, v33, pp. 1-27, 1985.

Digital Library

[6]

Goemans, M. X., "Worst-case comparison of valid inequalities for the TSP," Math. Programming, v69, pp. 335-349, 1995.

Digital Library

[7]

Grötschel, M., "On the monotone symmetric travelling salesman problem: Hypohamiltonian/hypotraceable graphs and facets," Math. Oper. Res., v5, pp. 285-292, 1980.

Digital Library

[8]

Grötschel, M., Lovász, L., Graham, R. L., Grötschel, M. and Lovász, L., "Combinatorial optimization," Handbook of Combinatorics, vII, North-Holland, Amsterdam, The Netherlands, pp. 1541-1597, 1995.

Digital Library

[9]

Grötschel, M. and Padberg, M. W., "On the symmetric travelling salesman problem I: Inequalities," Math. Programming, v16, pp. 265-280, 1979.

[10]

Grötschel, M. and Padberg, M. W., "On the symmetric travelling salesman problem II: Lifting theorems and facets," Math. Programming, v16, pp. 281-302, 1979.

[11]

Grötschel, M. and Pulleyblank, W. R., "Clique tree inequalities and the symmetric travelling salesman problem," Math. Oper. Res., v11, pp. 537-569, 1986.

Digital Library

[12]

Jünger, M., Reinelt, G., Rinaldi, G., Ball, M. O., Magnanti, T. L., Monma, C. L. and Nemhauser, G. L., "The traveling salesman problem," Network Models, Handbooks in Operations Research and Management Science, v7, North-Holland, Amsterdam, The Netherlands, pp. 225-330, 1995.

[13]

Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G. and Shmoys, D. B., The Traveling Salesman Problem. Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Chichester, 1985.

[14]

Naddef, D., Gutin, G. and Punnen, A., "Polyhedral theory, branch and cut algorithms for the symmetric traveling salesman problem," The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, Kluwer Academic Publisher, Dordrecht, The Netherlands, pp. 29-116, 2002.

[15]

Naddef, D. and Pochet, Y., "The symmetric traveling salesman polytope revisited," Math. Oper. Res., v26, pp. 700-722, 2001.

Digital Library

[16]

Naddef, D. and Rinaldi, G., "The symmetric traveling salesman polytope: New facets from the graphical relaxation," 1988.

[17]

Naddef, D. and Rinaldi, G., "The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities," Math. Programming, v51, pp. 359-400, 1991.

Digital Library

[18]

Naddef, D. and Rinaldi, G., "The graphical relaxation: A new framework for the symmetric traveling salesman polytope," Math. Programming, v58, pp. 53-88, 1993.

Digital Library

[19]

Naddef, D. and Thienel, S., "Efficient separation routines for the symmetric traveling salesman problem. I: General tools and comb separation," Math. Programming, v92, pp. 237-255, 2002.

[20]

Naddef, D. and Thienel, S., "Efficient separation routines for the symmetric traveling salesman problem. II: Separating multihandle inequalities," Math. Programming, v92, pp. 257-283, 2002.

[21]

Naddef, D. and Wild, E., "The domino inequalities: Facets for the symmetric traveling salesman polytope," Math. Programming, v98, pp. 223-251, 2003.

Digital Library

[22]

Nemhauser, G. L. and Wolsey, L. A., Integer and Combinatorial Optimization. Discrete Mathematics and Optimization, Wiley-Interscience, New York, 1988.

Digital Library

[23]

Oswald, M., Reinelt, G., Theis, D. O., Jünger, M. and Kaibel, V., "Not every GTSP facet induces a STSP facet," Integer Programming & Combinatorial Optimization (IPCO) XI, Lecture Notes in Computer Science, v3509, Springer-Verlag GmbH, Berlin, Germany, pp. 468-482, 2005.

Digital Library

[24]

Padberg, M. W. and Hong, S., "On the symmetric travelling salesman problem: A computational study," Math. Programming Stud., v12, pp. 78-107, 1980.

Cited By

Cook WEspinoza DGoycoolea M(2010)Generalized Domino-Parity Inequalities for the Symmetric Traveling Salesman ProblemMathematics of Operations Research10.5555/1858327.185832835:2(479-493)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.5555/1858327.1858328
Applegate DBixby RChváTal VCook WEspinoza DGoycoolea MHelsgaun K(2009)Certification of an optimal TSP tour through 85,900 citiesOperations Research Letters10.1016/j.orl.2008.09.00637:1(11-15)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1016/j.orl.2008.09.006

Index Terms

The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

The Binested Inequalities for the Symmetric Traveling Salesman Polytope

In this paper we define a family of valid inequalities for the Symmetric Travelling Salesman Polytope which are defined on two nested sets of vertices of the graph. These inequalities generalize the comb inequalities of Chvítal, Grötschel and Padberg, ...
The Symmetric Traveling Salesman Polytope Revisited

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 ...
The Crown Inequalities for the Symmetric Traveling Salesman Polytope

We define a new family of valid inequalities for the Symmetric Traveling Salesman Polytope STSP n , that is, the convex hull of the incidence vectors of all Hamiltonian cycles of a complete graph with n nodes. The smallest value of n for which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 32, Issue 1

February 2007

256 pages

ISSN:0364-765X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 February 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cook WEspinoza DGoycoolea M(2010)Generalized Domino-Parity Inequalities for the Symmetric Traveling Salesman ProblemMathematics of Operations Research10.5555/1858327.185832835:2(479-493)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.5555/1858327.1858328
Applegate DBixby RChváTal VCook WEspinoza DGoycoolea MHelsgaun K(2009)Certification of an optimal TSP tour through 85,900 citiesOperations Research Letters10.1016/j.orl.2008.09.00637:1(11-15)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1016/j.orl.2008.09.006

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents