Article ID: | iaor19971139 |
Country: | Netherlands |
Volume: | 68 |
Issue: | 3 |
Start Page Number: | 241 |
End Page Number: | 265 |
Publication Date: | Mar 1995 |
Journal: | Mathematical Programming (Series A) |
Authors: | Fischetti Matteo, Balas Egon, Pulleyblank William R. |
Many applications of the traveling salesman problem require the introduction of additional constraints. One of the most frequently occurring classes of such constraints are those requiring that certain cities be visited before others (precedence constraints). In this paper the authors study the Precedence-Constrained Asymmetric Traveling Salesman (PCATS) polytope, i.e. the convex hull of incidence vectors of tours in a precedence-constrained directed graph. They derive several families of valid inequalities, and give polynomial time separation algorithms for important subfamilies. The authors then establish the dimension of the PCATS polytope and show that, under reasonable assumptions, the two main classes of inequalities derived are facet inducing.