Combining and projecting flow models 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 | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | PESNEAU, Pierre | |
| hal.structure.identifier | Austrian Institute of Technology [Vienna] [AIT] | |
| dc.contributor.author | RUTHMAIR, Mario | |
| hal.structure.identifier | Centro de Investigação Operacional [CIO] | |
| dc.contributor.author | SANTOS, Daniel | |
| dc.date.accessioned | 2024-04-04T03:07:49Z | |
| dc.date.available | 2024-04-04T03:07:49Z | |
| dc.date.issued | 2017 | |
| dc.identifier.issn | 0028-3045 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193479 | |
| dc.description.abstractEn | There are many ways of modeling the Asymmetric Traveling Salesman Problem (ATSP) and the related Precedence Constrained ATSP (PCATSP). In this paper we present new formulations for the two problems that result from combining precedence variable based formulations with network flow based formulations. The motivation for this work is a property of the so-called GDDL inequalities (see Gouveia and Pesneau, 2006), the " disjoint sub-paths " property, that is explored to create formulations that combine two (or more) disjoint path network flow based formulations. Several sets of projected inequalities, in the space of the arc and precedence variables, and in the spirit of many inequalities presented in Gouveia and Pesneau (2006), are obtained by projecting these network flow based formulations. Computational results are given for the PCATSP and the ATSP to evaluate the quality of the new inequalities. | |
| dc.language.iso | en | |
| dc.publisher | Wiley | |
| dc.subject.en | integer linear programming | |
| dc.subject.en | precedence constraints | |
| dc.subject.en | traveling salesman | |
| dc.subject.en | reformulation | |
| dc.subject.en | cutting plane algorithm | |
| dc.subject.en | valid inequalities | |
| dc.title.en | Combining and projecting flow models for the (Precedence Constrained) Asymmetric Traveling Salesman Problem | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1002/net.21765 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| dc.subject.hal | Informatique [cs]/Mathématique discrète [cs.DM] | |
| bordeaux.journal | Networks | |
| bordeaux.page | 451-465 | |
| bordeaux.volume | 71 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 4 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01655793 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01655793v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Networks&rft.date=2017&rft.volume=71&rft.issue=4&rft.spage=451-465&rft.epage=451-465&rft.eissn=0028-3045&rft.issn=0028-3045&rft.au=GOUVEIA,%20Lu%C3%ADs&PESNEAU,%20Pierre&RUTHMAIR,%20Mario&SANTOS,%20Daniel&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||