Essec\Faculty\Model\Contribution {#2233 ▼
#_index: "academ_contributions"
#_id: "10549"
#_source: array:26 [
"id" => "10549"
"slug" => "10549-hop-constrained-steiner-trees-with-multiple-root-nodes"
"yearMonth" => "2014-06"
"year" => "2014"
"title" => "Hop constrained Steiner trees with multiple root nodes"
"description" => "GOUVEIA, L., LEITNER, M. et LJUBIC, I. (2014). Hop constrained Steiner trees with multiple root nodes. <i>European Journal of Operational Research</i>, 236(1), pp. 100-112. 
GOUVEIA, L., LEITNER, M. et LJUBIC, I. (2014). Hop constrained Steiner trees with multiple root node "
"authors" => array:3 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "GOUVEIA Luis"
]
2 => array:1 [
"name" => "LEITNER Markus"
]
]
"ouvrage" => ""
"keywords" => array:4 [
0 => "Integer programming"
1 => "OR in telecommunications"
2 => "Steiner tree"
3 => "Hop-constraints"
]
"updatedAt" => "2021-07-13 14:31:38"
"publicationUrl" => "https://doi.org/10.1016/j.ejor.2013.11.029"
"publicationInfo" => array:3 [
"pages" => "100-112"
"volume" => "236"
"number" => "1"
]
"type" => array:2 [
"fr" => "Articles"
"en" => "Journal articles"
]
"support_type" => array:2 [
"fr" => "Revue scientifique"
"en" => "Scientific journal"
]
"countries" => array:2 [
"fr" => null
"en" => null
]
"abstract" => array:2 [
"fr" => "We consider a network design problem that generalizes the hop and diameter constrained Steiner tree problem as follows: Given an edge-weighted undirected graph with two disjoint subsets representing roots and terminals, find a minimum-weight subtree that spans all the roots and terminals so that the number of hops between each relevant node and an arbitrary root does not exceed a given hop limit H. The set of relevant nodes may be equal to the set of terminals, or to the union of terminals and root nodes. This article proposes integer linear programming models utilizing one layered graph for each root node. Different possibilities to relate solutions on each of the layered graphs as well as additional strengthening inequalities are then discussed. Furthermore, theoretical comparisons between these models and to previously proposed flow- and path-based formulations are given. To solve the problem to optimality, we implement branch-and-cut algorithms for the layered graph formulations. Our computational study shows their clear advantages over previously existing approaches. We consider a network design problem that generalizes the hop and diameter constrained Steiner tree "
"en" => "We consider a network design problem that generalizes the hop and diameter constrained Steiner tree problem as follows: Given an edge-weighted undirected graph with two disjoint subsets representing roots and terminals, find a minimum-weight subtree that spans all the roots and terminals so that the number of hops between each relevant node and an arbitrary root does not exceed a given hop limit H. The set of relevant nodes may be equal to the set of terminals, or to the union of terminals and root nodes. This article proposes integer linear programming models utilizing one layered graph for each root node. Different possibilities to relate solutions on each of the layered graphs as well as additional strengthening inequalities are then discussed. Furthermore, theoretical comparisons between these models and to previously proposed flow- and path-based formulations are given. To solve the problem to optimality, we implement branch-and-cut algorithms for the layered graph formulations. Our computational study shows their clear advantages over previously existing approaches. We consider a network design problem that generalizes the hop and diameter constrained Steiner tree "
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2025-04-02T10:21:47.000Z"
"docTitle" => "Hop constrained Steiner trees with multiple root nodes"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, GOUVEIA Luis, LEITNER Markus"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, GOUVEIA Luis, LEITNER Markus</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2014</span> <span class="document-property-authors">LJUBIC Ivana, GOUVEIA Luis, LEITNER Markus</span><br><span c "
"keywordList" => "<a href="#">Integer programming</a>, <a href="#">OR in telecommunications</a>, <a href="#">Steiner tree</a>, <a href="#">Hop-constraints</a> <a href="#">Integer programming</a>, <a href="#">OR in telecommunications</a>, <a href="#">Steiner t "
"docPreview" => "<b>Hop constrained Steiner trees with multiple root nodes</b><br><span>2014-06 | Articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://doi.org/10.1016/j.ejor.2013.11.029" target="_blank">Hop constrained Steiner trees with multiple root nodes</a> <a href="https://doi.org/10.1016/j.ejor.2013.11.029" target="_blank">Hop constrained Steiner trees w "
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.969202
+"parent": null
}
