Show simple item record

Distance transformation for network design problems

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.identifierLaboratoire d'Informatique de Robotique et de Microélectronique de Montpellier [LIRMM]
dc.contributor.authorPoss, Michael
HAL ID: 170284
ORCID: 0000-0002-9145-2525		*
hal.structure.identifierFederal University of Rio de Janeiro
dc.contributor.authorSimonetti, Luidi*
hal.structure.identifierautre
dc.contributor.authorUchoa, Eduardo*
dc.date.accessioned2019-10-09T09:32:15Z
dc.date.available2019-10-09T09:32:15Z
dc.date.issued2019
dc.identifier.issn1052-6234
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20054
dc.language.isoenen
dc.subjectExtended Formulationsen
dc.subjectNetwork Designen
dc.subjectBenders decompositionen
dc.subject.ddc004en
dc.titleDistance transformation for network design problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe propose a new generic way to construct extended formulations for a large class of network design problems with given connectivity requirements. The approach is based on a graph transformation that maps any graph into a layered graph according to a given distance function. The original connectivity requirements are in turn transformed into equivalent connectivity requirements in the layered graph. The mapping is extended to the graphs induced by fractional vectors through an extended linear integer programming formulation. While graphs induced by binary vectors are mapped to isomorphic layered graphs, those induced by fractional vectors are mapped to a set of graphs having worse connectivity properties. Hence, the connectivity requirements in the layered graph may cut off fractional vectors that were feasible for the problem formulated in the original graph. Experiments over instances of the Steiner forest and hop-constrained survivable network design problems show that significant gap reductions compared with state-of-the art formulations can be obtained.en
dc.relation.isversionofjnlnameSIAM Journal on Optimization
dc.relation.isversionofjnlvol29en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2019
dc.relation.isversionofjnlpages1687-1713en
dc.relation.isversionofdoi10.1137/16M1108261en
dc.relation.isversionofjnlpublisherSIAM - Society for Industrial and Applied Mathematicsen
dc.subject.ddclabelInformatique généraleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-10-09T09:25:22Z
hal.faultCode{"duplicate-entry":{"hal-01632972":{"doi":"1.0"}}}
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
Distance_Transformation.pdf
Size:
800.9Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record