A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets

摘要: Given any family ℱ of valid inequalities for the asymmetric traveling salesman polytopeP(G) defined on complete digraphG, we show that all members are facet defining if primitive (usually a small subclass) are. Based this result then introduce general procedure identifying new classes inducing forP(G) by lifting forP(G′), whereG′ is some induced subgraph ofG. Unlike traditional lifting, where lifted coefficients calculated one and their value depends sequence, our replaces nodes ofG′ with cliques ofG uses closed form expressions calculating arcs, which sequence-independent. We also class inequalities, SD (source-destination) subsumes as special cases most known families inequalities.