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 (us ually a small subclass) are. Based on this result we then introduce a general procedure for identifying new classes of facet inducing inequa lities for P(G) by lifting inequalities that are facet inducing for P( G'), where G' is some induced subgraph of G. Unlike traditional liftin g, where the lifted coefficients are calculated one by one and their v alue depends on the lifting sequence, our lifting procedure replaces n odes of G' with cliques of G and uses closed form expressions for calc ulating the coefficients of the new arcs, which are sequence-independe nt. We also introduce a new class of facet inducing inequalities, the class of SD (source-destination) inequalities, which subsumes as speci al cases most known families of facet defining inequalities.