On extended formulations for the precedence constrained asymmetric traveling salesman problem

Luis Gouveia 1 Pierre Pesneau 2, 3
3 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
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.
Type de document :
Article dans une revue
Networks, Wiley, 2006, 48 (2), pp.77-89. 〈10.1002/net.20122〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00281586
Contributeur : Pierre Pesneau <>
Soumis le : mardi 5 décembre 2017 - 14:20:24
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Fichier

PCATSP_Article.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Luis Gouveia, Pierre Pesneau. On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks, Wiley, 2006, 48 (2), pp.77-89. 〈10.1002/net.20122〉. 〈inria-00281586〉

Partager

Métriques

Consultations de la notice

242

Téléchargements de fichiers

28