Show simple item record

Hop-level flow formulation for the survivable network design with hop constraints problem

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMahjoub, Ali Ridha*
hal.structure.identifier
dc.contributor.authorSimonetti, Luidi*
hal.structure.identifier
dc.contributor.authorUchoa, Eduardo*
dc.date.accessioned2013-06-18T07:55:13Z
dc.date.available2013-06-18T07:55:13Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11430
dc.language.isoenen
dc.subjectnetwork designen
dc.subjectsurvivabilityen
dc.subjectextended formulationsen
dc.subject.ddc004en
dc.titleHop-level flow formulation for the survivable network design with hop constraints problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe 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.isversionofjnlnameNetworks
dc.relation.isversionofjnlvol61en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages171-179en
dc.relation.isversionofdoi10.1002/net.21483en
dc.relation.isversionofjnlpublisherWileyen
dc.subject.ddclabelInformatique généraleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01497005*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record