dc.contributor.author | Mahjoub, Ali Ridha | * |
dc.contributor.author | Simonetti, Luidi | * |
dc.contributor.author | Uchoa, Eduardo | * |
dc.date.accessioned | 2013-06-18T07:55:13Z | |
dc.date.available | 2013-06-18T07:55:13Z | |
dc.date.issued | 2013 | |
dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/11430 | |
dc.language.iso | en | en |
dc.subject | network design | en |
dc.subject | survivability | en |
dc.subject | extended formulations | en |
dc.subject.ddc | 004 | en |
dc.title | Hop-level flow formulation for the survivable network design with hop constraints problem | en |
dc.type | Article accepté pour publication ou publié | |
dc.description.abstracten | The hop-constrained survivable network design problem consists of finding a minimum cost subgraph containing K edge-disjoint paths with length at most H joining each pair of vertices in a given demand set. When all demands have a common vertex, the instance is said to be rooted. We propose a new extended formulation for the rooted case, called hop-level multicommodity flow (MCF), that can be significantly stronger than the previously known formulations, at the expense of having a larger number of variables and constraints, growing linearly with the number of edges and demands and quadratically with H. However, for the particular case where H = 2, it can be specialized into a very compact and efficient formulation. Even when H = 3, hop-level-MCF can still be quite efficient and it has solved several instances from the literature for the first time. | en |
dc.relation.isversionofjnlname | Networks | |
dc.relation.isversionofjnlvol | 61 | en |
dc.relation.isversionofjnlissue | 2 | en |
dc.relation.isversionofjnldate | 2013 | |
dc.relation.isversionofjnlpages | 171-179 | en |
dc.relation.isversionofdoi | 10.1002/net.21483 | en |
dc.relation.isversionofjnlpublisher | Wiley | en |
dc.subject.ddclabel | Informatique générale | en |
dc.relation.forthcoming | non | en |
dc.relation.forthcomingprint | non | en |
dc.description.halcandidate | oui | |
dc.description.readership | recherche | |
dc.description.audience | International | |
dc.relation.Isversionofjnlpeerreviewed | oui | |
hal.person.labIds | 989 | * |
hal.person.labIds | | * |
hal.person.labIds | | * |
hal.identifier | hal-01497005 | * |