On extended formulations for the precedence constrained asymmetric traveling salesman problem
PESNEAU, Pierre
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
PESNEAU, Pierre
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Réduire
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Langue
en
Article de revue
Ce document a été publié dans
Networks. 2006, vol. 48, n° 2, p. 77-89
Wiley
Résumé en anglais
In this paper we study the use of formulations with precedence relationvariables for the Precedence Constrained Asymmetric Travelling Salesman(PCATS) problem. Contrary to previous papers, the emphasis of this paperis on ...Lire la suite >
In this paper we study the use of formulations with precedence relationvariables for the Precedence Constrained Asymmetric Travelling Salesman(PCATS) problem. Contrary to previous papers, the emphasis of this paperis on formulations involving exponential sized sets of inequalities and onthe development of a cutting plane method together with polynomial routinesfor separating the new inequalities. Our computational results, taken from aset of benchmark instances, show that our methods improve significantly onmost of the best previously known lower bound values.< Réduire
Mots clés en anglais
Asymetric traveling salesman problem
Precedence constraints
Projection
Cutting plane
Origine
Importé de halUnités de recherche