The precedence-constrained asymmetric traveling salesman polytope

The precedence-constrained asymmetric traveling salesman polytope

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.