Essec\Faculty\Model\Contribution {#6196
#_index: "academ_contributions"
#_id: "565"
#_source: array:26 [
"id" => "565"
"slug" => "a-node-based-layered-graph-approach-for-the-steiner-tree-problem-with-revenues-budget-and-hop-constraints"
"yearMonth" => "2016-12"
"year" => "2016"
"title" => "A Node-Based Layered Graph Approach for the Steiner Tree Problem with Revenues, Budget and Hop-Constraints"
"description" => "SINNL, M. et LJUBIC, I. (2016). A Node-Based Layered Graph Approach for the Steiner Tree Problem with Revenues, Budget and Hop-Constraints. <i>Mathematical Programming Computation</i>, 8(4), pp. 461–490."
"authors" => array:2 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "SINNL M."
]
]
"ouvrage" => ""
"keywords" => array:6 [
0 => "Mixed integer programming"
1 => "Exact computation"
2 => "Hop-constrained trees"
3 => "Branch-and-cut"
4 => "Layered graph"
5 => "Node-based model"
]
"updatedAt" => "2021-09-24 10:33:27"
"publicationUrl" => "https://link.springer.com/article/10.1007/s12532-016-0102-1"
"publicationInfo" => array:3 [
"pages" => "461–490"
"volume" => "8"
"number" => "4"
]
"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" => "The Steiner tree problem with revenues, budget and hop-constraints (STPRBH) is a variant of the classical Steiner tree problem. The goal is to find a tree maximizing the collected revenue, which is associated with nodes, subject to a given budget for the edge cost of the tree and a hop-limit for the distance between the given root node and any other node in that tree. In this work, we introduce a novel generic way to model hop-constrained tree problems as integer linear programs and apply it to the STPRBH. Our approach is based on the concept of layered graphs that gained widespread attention in the recent years, due to their computational advantage when compared to previous formulations for modeling hop-constraints. Contrary to previous MIP formulations based on layered graphs (that are arc-based models), our model is node-based. Thus it contains much less variables and allows to tackle large-scale instances and/or instances with large hop-limits, for which the size of arc-based layered graph models may become prohibitive. The aim of our model is to provide a good compromise between quality of root relaxation bounds and the size of the underlying MIP formulation. We implemented a branch-and-cut algorithm for the STPRBH based on our new model. Most of the instances available for the DIMACS challenge, including 78 (out of 86) previously unsolved ones, can be solved to proven optimality within a time limit of 1000 s, most of them being solved within a few seconds only. These instances contain up to 500 nodes and 12,500 edges, with hop-limit up to 25."
"en" => "The Steiner tree problem with revenues, budget and hop-constraints (STPRBH) is a variant of the classical Steiner tree problem. The goal is to find a tree maximizing the collected revenue, which is associated with nodes, subject to a given budget for the edge cost of the tree and a hop-limit for the distance between the given root node and any other node in that tree. In this work, we introduce a novel generic way to model hop-constrained tree problems as integer linear programs and apply it to the STPRBH. Our approach is based on the concept of layered graphs that gained widespread attention in the recent years, due to their computational advantage when compared to previous formulations for modeling hop-constraints. Contrary to previous MIP formulations based on layered graphs (that are arc-based models), our model is node-based. Thus it contains much less variables and allows to tackle large-scale instances and/or instances with large hop-limits, for which the size of arc-based layered graph models may become prohibitive. The aim of our model is to provide a good compromise between quality of root relaxation bounds and the size of the underlying MIP formulation. We implemented a branch-and-cut algorithm for the STPRBH based on our new model. Most of the instances available for the DIMACS challenge, including 78 (out of 86) previously unsolved ones, can be solved to proven optimality within a time limit of 1000 s, most of them being solved within a few seconds only. These instances contain up to 500 nodes and 12,500 edges, with hop-limit up to 25."
]
"authors_fields" => array:2 [
"fr" => "Systèmes d’Information, Sciences de la Décision et Statistiques"
"en" => "Information Systems, Decision Sciences and Statistics"
]
"indexedAt" => "2024-04-18T13:22:00.000Z"
"docTitle" => "A Node-Based Layered Graph Approach for the Steiner Tree Problem with Revenues, Budget and Hop-Constraints"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, SINNL M."
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, SINNL M.</span><br><span class="document-property-authors_fields">Systèmes d’Information, Sciences de la Décision et Statistiques</span> | <span class="document-property-year">2016</span>"
"keywordList" => "<a href="#">Mixed integer programming</a>, <a href="#">Exact computation</a>, <a href="#">Hop-constrained trees</a>, <a href="#">Branch-and-cut</a>, <a href="#">Layered graph</a>, <a href="#">Node-based model</a>"
"docPreview" => "<b>A Node-Based Layered Graph Approach for the Steiner Tree Problem with Revenues, Budget and Hop-Constraints</b><br><span>2016-12 | Articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://link.springer.com/article/10.1007/s12532-016-0102-1" target="_blank">A Node-Based Layered Graph Approach for the Steiner Tree Problem with Revenues, Budget and Hop-Constraints</a>"
]
+lang: "fr"
+"_type": "_doc"
+"_score": 9.170836
+"parent": null
}
