A LIFTING PROCEDURE FOR THE ASYMMETRIC TRAVELING SALESMAN POLYTOPE AND A LARGE NEW CLASS OF FACETS

Given any family F of valid inequalities for the asymmetric traveling salesman polytope P(G) defined on the complete digraph G, we show that all members of F are facet defining if the primitive members of F (usually a small subclass) are. Based on this result we then introduce a general procedure for identifying new classes of facet inducing inequalities for P(G) by lifting inequalities that are facet inducing for P(G'), where G' is some induced subgraph of G. 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 of G' with cliques of G 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.