Abstract
Given any family ℱ of valid inequalities for the asymmetric traveling salesman polytopeP(G) defined on the complete digraphG, we show that all members of ℱ are facet defining if the primitive members of ℱ (usually a small subclass) are. Based on this result we then introduce a general procedure for identifying new classes of facet inducing inequalities forP(G) by lifting inequalities that are facet inducing forP(G′), whereG′ is some induced subgraph ofG. Unlike traditional lifting, where the lifted coefficients are calculated one by one and their value depends on the lifting sequence, our lifting procedure replaces nodes ofG′ with cliques ofG and uses closed form expressions for calculating the coefficients of the new arcs, which are sequence-independent. We also introduce a new class of facet inducing inequalities, the class of SD (source-destination) inequalities, which subsumes as special cases most known families of facet defining inequalities.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. Balas, “The asymmetric assignment problem and some new facets of the traveling salesman polytope,”SIAM Journal on Discrete Mathematics 2 (1989) 425–451.
E. Balas, and M. Fischetti, “The fixed-outdegree 1-arborescence polytope,” to appear inMathematics of Operations Research.
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.
M. Fischetti, “Facets of the asymmetric traveling salesman polytope,”Mathematics of Operations Research 16 (1991) 42–56.
M. Grötschel,Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme (Hain, Maisenheim am Glan, 1977).
M. Grötschel and M. Padberg, “Lineare Charakterisierungen von Travelling Salesman Problemen,”Zeitschrift für Operations Research 21 (1977) 33–36.
M. Grötschel and M. Padberg, “Polyhedral theory,” in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D. Shmoys, eds.,The Traveling Salesman Problem (Wiley, New York, 1985) pp. 251–305.
M. Grötschel and W. Pulleyblank, “Clique tree inequalities and the symmetric traveling salesman problem,”Mathematics of Operations Research 11 (1986) 537–569.
M. Padberg and G. Rinaldi, “Facet identification for the symmetric traveling salesman polytope,”Mathematical Programming 47 (1990) 219–257.
Author information
Authors and Affiliations
Additional information
Research supported by Grant DDM-8901495 of the National Science Foundation and Contract N00014-85-K-0198 of the U.S. Office of Naval Research.
Research supported by M.U.R.S.T., Italy.
Rights and permissions
About this article
Cite this article
Balas, E., Fischetti, M. A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets. Mathematical Programming 58, 325–352 (1993). https://doi.org/10.1007/BF01581274
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01581274