On extended formulations for the precedence constrained asymmetric traveling salesman problem - Archive ouverte HAL Access content directly
Journal Articles Networks Year : 2006

On extended formulations for the precedence constrained asymmetric traveling salesman problem

(1) , (2, 3)
1
2
3

Abstract

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.
Fichier principal
Vignette du fichier
PCATSP_Article.pdf (283.96 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00281586 , version 1 (05-12-2017)

Identifiers

Cite

Luís Gouveia, Pierre Pesneau. On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks, 2006, 48 (2), pp.77-89. ⟨10.1002/net.20122⟩. ⟨inria-00281586⟩

Collections

CNRS INRIA INRIA2
117 View
145 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More