On extended formulations for the precedence constrained asymmetric traveling salesman problem
Résumé
In this paper we study the use of formulations with precedence relation
variables for the Precedence Constrained Asymmetric Travelling Salesman
(PCATS) problem. Contrary to previous papers, the emphasis of this paper
is on formulations involving exponential sized sets of inequalities and on
the development of a cutting plane method together with polynomial routines
for separating the new inequalities. Our computational results, taken from a
set of benchmark instances, show that our methods improve significantly on
most of the best previously known lower bound values.
Origine : Fichiers produits par l'(les) auteur(s)