Lifted cycle inequalities for the asymmetric traveling salesman problem

We investigate the family of facet defining inequalities for the asymmetric traveling salesman (ATS) polytope obtainable by lifting the cycle inequalities. We establish several properties of this family that earmark it as arguably the most important among the asymmetric inequalities for the ATS polytope known to date. In particular, we give several results that characterize the pattern of lifting coefficients and thereby facilitate the identification of facet defining inequalities. This characterization is used to investigate three new, large classes of lifted cycle inequalities that we call shell; fork and curtain inequalities. These latter inequalities have unbounded Chvatal rank. Furthermore, the pattern of lifting coefficients that we identify makes it easy to develop efficient separation routines. Finally, each member of the family is shown to have a counterpart for the symmetric TS (STS) polytope that is often new, and is obtainable by mapping the inequality for the ATS polytope into a certain face of the STS polytope and then lifting the resulting inequality into one for the STS polytope itself.