THE PRECEDENCE-CONSTRAINED ASYMMETRIC TRAVELING SALESMAN POLYTOPE

Many applications of the traveling salesman problem require the introd uction of additional constraints. One of the most frequently occurring classes of such constraints are those requiring that certain cities b e visited before others (precedence constraints). In this paper we stu dy the Precedence-Constrained Asymmetric Traveling Salesman (PCATS) po lytope, i.e. the convex hull of incidence vectors of tours in a preced ence-constrained directed graph. We derive several families of valid i nequalities, and give polynomial time separation algorithms for import ant subfamilies. We then establish the dimension of the PCATS polytope and show that, under reasonable assumptions, the two main classes of inequalities derived are facet inducing.