On extended formulations for the precedence constrained asymmetric traveling salesman problem
| hal.structure.identifier | Centro de Investigação Operacional [CIO] | |
| dc.contributor.author | GOUVEIA, Luís | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | PESNEAU, Pierre | |
| dc.date.accessioned | 2024-04-04T03:07:48Z | |
| dc.date.available | 2024-04-04T03:07:48Z | |
| dc.date.issued | 2006 | |
| dc.identifier.issn | 0028-3045 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193477 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | Wiley | |
| dc.subject.en | Asymetric traveling salesman problem | |
| dc.subject.en | Precedence constraints | |
| dc.subject.en | Projection | |
| dc.subject.en | Cutting plane | |
| dc.title.en | On extended formulations for the precedence constrained asymmetric traveling salesman problem | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1002/net.20122 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | Networks | |
| bordeaux.page | 77-89 | |
| bordeaux.volume | 48 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 2 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00281586 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00281586v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Networks&rft.date=2006&rft.volume=48&rft.issue=2&rft.spage=77-89&rft.epage=77-89&rft.eissn=0028-3045&rft.issn=0028-3045&rft.au=GOUVEIA,%20Lu%C3%ADs&PESNEAU,%20Pierre&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||