Show simple item record

k-node-disjoint hop-constrained survivable networks: polyhedral analysis and branch and cut

hal.structure.identifierLaboratoire de Mathématiques Appliquées du Havre [LMAH]
dc.contributor.authorDiarrassouba, Ibrahima
HAL ID: 745402		*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMahjoub, Meriem*
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.identifierUniversite Bilkent [Ankara]
dc.contributor.authorYaman, Hande*
dc.date.accessioned2020-05-13T15:10:25Z
dc.date.available2020-05-13T15:10:25Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20732
dc.language.isoenen
dc.subjectk-node-disjoint hop-constrained pathsen
dc.subjectSurvivable networken
dc.subjectPolytopeen
dc.subjectValid inequalitiesen
dc.subjectFacetsen
dc.subjectSeparationen
dc.subjectBranch-and-cuten
dc.subject.ddc511en
dc.titlek-node-disjoint hop-constrained survivable networks: polyhedral analysis and branch and cuten
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven a graph with weights on the edges, a set of origin and destination pairs of nodes, and two integers L ≥ 2 and k ≥ 2, the k-node-disjoint hop-constrained network design problem is to find a minimum weight subgraph of G such that between every origin and destination there exist at least k node-disjoint paths of length at most L. In this paper, we consider this problem from a polyhedral point of view. We propose an integer linear programming formulation for the problem for L ∈{2,3} and arbitrary k, and investigate the associated polytope. We introduce new valid inequalities for the problem for L ∈{2,3,4}, and give necessary and sufficient conditions for these inequalities to be facet defining. We also devise separation algorithms for these inequalities. Using these results, we propose a branch-and-cut algorithm for solving the problem for both L = 3 and L = 4 along with some computational results.en
dc.relation.isversionofjnlnameAnnals of Telecommunications - annales des télécommunications
dc.relation.isversionofjnlvol73en
dc.relation.isversionofjnldate2018-01
dc.relation.isversionofjnlpages5-28en
dc.relation.isversionofdoi10.1007/s12243-017-0622-3en
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-05-13T15:03:27Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
knode_disjoint.pdf
Size:
3.739Mb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record