Abstract
A present trend in the study of theSymmetric Traveling Salesman Polytope (STSP(n)) is to use, as a relaxation of the polytope, thegraphical relaxation (GTSP(n)) rather than the traditionalmonotone relaxation which seems to have attained its limits. In this paper, we show the very close relationship between STSP(n) and GTSP(n). In particular, we prove that every non-trivial facet of STSP(n) is the intersection ofn + 1 facets of GTSP(n),n of which are defined by the degree inequalities. This fact permits us to define a standard form for the facet-defining inequalities for STSP(n), that we calltight triangular, and to devise a proof technique that can be used to show that many known facet-defining inequalities for GTSP(n) define also facets of STSP(n). In addition, we give conditions that permit to obtain facet-defining inequalities by composition of facet-defining inequalities for STSP(n) and general lifting theorems to derive facet-defining inequalities for STSP(n +k) from inequalities defining facets of STSP(n).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
X. Berenguer, “A characterization of linear admissible transformations for them-travelling salesmen problem,”European Journal of Operational Research 3 (1979) 232–249.
S. Boyd, private communication (1988).
S. Boyd and W.H. Cunningham, “Small travelling salesman polytopes,”Mathematics of Operations Research 16 (1991) 259–271.
V. Chvátal, “Edmonds polytopes and weakly Hamiltonian graphs,”Mathematical Programming 5 (1973), 29–40.
G. Cornuéjols, J. Fonlupt and D. Naddef, “The traveling salesman problem on a graph and some related integer polyhedra,”Mathematical Programming 33 (1985) 1–27.
T. Christof, M. Jünger and G. Reinelt, “A complete description of the traveling salesman polytope on 8 nodes,”Operations Research Letters 10 (1991) 497–500.
G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, “Solution of a large-scale travelling salesman problem,”Operations Research 2 (1954) 393–410.
J. Edmonds, “Maximum matching and a polyhedron with 0, 1-vertices,”Journal of Research of the National Bureau of Standards, Section B 69 (1965) 125–130.
B. Fleischmann, “A new class of cutting planes for the symmetric travelling salesman problem,”Mathematical Programming 40 (1988) 225–246.
M. Hartman, private communication (1988).
M. Grötschel and O. Holland, “Solution of large-scale symmetric travelling salesman problems,”Mathematical Programming 15 (1991) 141–202.
M. Grötschel and M. Padberg, “On the symmetric travelling salesman problem,” working paper, Institut für Oekonometrie und Operation Research, Universität Bonn (1975).
M. Grötschel and M. Padberg, “On the symmetric travelling salesman problem I: Inequalities,”Mathematical Programming 16 (1979) 265–280.
M. Grötschel and M. Padberg, “On the symmetric travelling salesman problem II: Lifting theorems and facets,”Mathematical Programming 16 (1979) 281–302.
M. Grötschel and M. Padberg, “Polyhedral theory,” in: E.L. Lawler et al., eds.,The Traveling Salesman Problem (Wiley, Chichester, 1985) pp. 251–305.
M. Grötschel and W.R. Pulleyblank, “Clique tree inequalities and the symmetric travelling salesman problem,”Mathematics of Operations Research 11 (1986) 537–569.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Traveling Salesman Problem (Wiley, Chichester, 1985).
J.F. Maurras, “Some results on the convex hull of Hamiltonian cycles of symmetric complete graphs,” in: B. Roy, ed.,Combinatorial Programming: Methods and Applications (Reidel, Dordrecht, 1975) pp. 179–190.
D. Naddef and G. Rinaldi, “The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities,”Mathematical Programming 51 (1991) 359–400.
D. Naddef and G. Rinaldi, “The symmetric traveling salesman polytope: New facets from the graphical relaxation,” Report R.248, IASI-CNR (Rome, 1988).
D. Naddef and G. Rinaldi, “The crown inequalities for the symmetric traveling salesman polytope,”Mathematics of Operations Research 17 (1992) 308–326.
G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization (Wiley, Chicester, 1988).
M. Padberg, “On the facial structure of the set packing polyhedra,”Mathematical Programming 5 (1973) 199–216.
M. Padberg and M. Grötschel, “Polyhedral computations,” in: E.L. Lawler et al., eds.,The Traveling Salesman Problem (Wiley, Chichester, 1985) pp. 307–360.
M. Padberg and S. Hong, “On the symmetric travelling salesman problem: A computational study,”Mathematical Programming Study 12 (1980) 78–107.
M. Padberg and G. Rinaldi, “Optimization of a 532-city symmetric traveling salesman problem by branch-and-cut,”Operations Research Letters 6 (1987) 1–7.
M. Padberg and G. Rinaldi, “Facet identification for the symmetric traveling salesman polytope,”Mathematical Programming 47 (1990) 219–257.
M. Padberg and G. Rinaldi, “A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems,”SIAM Review 33 (1991) 60–100.
W.R. Pulleyblank, “Polyhedral combinatorics,” in: A. Bachem et al., eds.,Mathematical Programming: The State of the Art - Bonn 1982 (Springer, Berlin, 1983) pp. 312–345.
M. Queyranne and Y. Wang, private communication (1989).
H. Weyl, “Elementare Theorie der konvexen Polyeder,”Commentarii Mathematici Helvetici 7 (1935) 509–533.
Author information
Authors and Affiliations
Additional information
Partially financed by P.R.C. Mathématique et Informatique.
Rights and permissions
About this article
Cite this article
Naddef, D., Rinaldi, G. The graphical relaxation: A new framework for the symmetric traveling salesman polytope. Mathematical Programming 58, 53–88 (1993). https://doi.org/10.1007/BF01581259
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01581259