A procedure of facet composition for the symmetric traveling salesman polytope
Abstract
We propose a new procedure of facet composition for the Symmetric Traveling Salesman Polytope(STSP). Applying this procedure to the well-known comb inequalities, we obtain completely or partially known classes of inequalities like clique-tree, star, hyperstar, ladder inequalities for STSP. This provides a proof that a large subset of hyperstar inequalities which are until now only known to be valid, are indeed facets defining inequalities of STSP and this also generalizes ladder inequalities to a larger class. Finally, we describe some new facet defining inequalities obtained by applying the procedure.
References
[1]
1. S. Boyd, W. Cunningham, M. Queyranne, and Y. Wang. Ladders for travelling salesmen. SIAM Journal on Optimization, 5:408-420, 1995.
[2]
2. V. Chvátal. Edmonds polytopes and weakly hamiltonian graphs. Mathematical Programming, 5:29-40, 1973.
[3]
3. B. Fleischman. Cutting planes for the symmetric traveling salesman problem. Technical report, Universitat Hamburg, 1987.
[4]
4. B. Fleischman. A new class of cutting planes for the symmetric travelling salesman problem. Mathematical Programming, 40:225-246, 1988.
[5]
5. M. Grötschel and M. Padberg. On the symmetric traveling salesman problem I: inequalities. Mathematical Programming, 16:265-280, 1979.
[6]
6. M. Grötschel and W. Pulleyblank. Clique tree inequalities and the symmetric traveling salesman problem. Mathematics of operations research, 11:537-569, 1986.
[7]
7. M. Jünger, G. Reinelt, and G. Rinaldi. The traveling salesman problem. In M. Ball, T. Magnanti, C. Monma, and G. Nemhauser, editors, Handbook on Operations Research and Management Science, pages 225-330. North Holland, 1995.
[8]
8. D. Naddef and G. Rinaldi. The symmetric traveling salesman polytope: new facets from the graphical relaxation. Technical Report 248, Instituto di Analisi dei Sistemi ed Informatica, 1988.
[9]
9. D. Naddef and G. Rinaldi. The graphical relaxation: a new framework for the symmetric traveling salesman polytope. Mathematical Programming, 58:53-88, 1993.
[10]
10. D. Naddef. Handles and teeth in the symmetric traveling salesman polytope. In W. Cook and P. Seymour, editors, Polyhedral Combinatorics, volume 1, pages 61-74. DIMACS series in Discrete Mathematics and Theoretical of Computer Science, AMS-ACM, 1990.
[11]
11. V. H. Nguyen. Polyèdres de cycles : Description, Composition et Lifting de Facettes. PhD thesis, Université de la Méditerranée, Marseille, 2000.
[12]
12. M. Queyranne and Y. Wang. Facet-tree composition for symmetric travelling salesman polytopes. Technical Report 90-MSC-001, Faculty of Commerce and Business Administration, University of British Columbia, 1990.
[13]
13. M. Queyranne and Y. Wang. Composing facets of symmetric travelling salesman polytopes. Technical report, Faculty of Commerce and Business Administration, University of British Columbia, 1991.
Index Terms
- A procedure of facet composition for the symmetric traveling salesman polytope
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
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 January 2003
Qualifiers
- Chapter
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025