Abstract
Four lifting theorems are derived for the symmetric travelling salesman polytope. They provide constructions and state conditions under which a linear inequality which defines a facet of then-city travelling salesman polytope retains its facetial property for the (n + m)-city travelling salesman polytope, wherem ≥ 1 is an arbitrary integer. In particular, they permit a proof that all subtour-elimination as well as comb inequalities define facets of the convex hull of tours of then-city travelling salesman problem, wheren is an arbitrary integer.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
V. Chvátal, “Edmonds polytopes and weakly Hamiltonian graphs”,Mathematical Programming 5 (1973) 29–40.
M. Grötschel, “Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme”, Dissertation, University of Bonn, 1977 (Verlag A. Hain, Meisenheim, 1977).
M. Grötschel and M.W. Padberg, “On the symmetric travelling salesman problem I: Inequalities”,Mathematical Programming (1979) 265–280 (this issue).
J.F. Maurras, “Polytopes à sommets dans [0, 1]n”, Thèse, University of Paris (Paris, 1976).
M.W. Padberg and S. Hong, “On the symmetric travelling salesman problem: A computational study”, T.J. Watson Research Center, IBM Research (Yorktown Heights, NY, 1977).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Grötschel, M., Padberg, M.W. On the symmetric travelling salesman problem II: Lifting theorems and facets. Mathematical Programming 16, 281–302 (1979). https://doi.org/10.1007/BF01582117
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582117