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]
< Reduce
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Language
en
Article de revue
This item was published in
Networks. 2006, vol. 48, n° 2, p. 77-89
Wiley
English Abstract
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 ...Read more >
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.Read less <
English Keywords
Asymetric traveling salesman problem
Precedence constraints
Projection
Cutting plane
Origin
Hal imported