Essec\Faculty\Model\Contribution {#2216
#_index: "academ_contributions"
#_id: "564"
#_source: array:26 [
"id" => "564"
"slug" => "a-node-based-ilp-formulation-for-the-node-weighted-dominating-steiner-problem"
"yearMonth" => "2017-01"
"year" => "2017"
"title" => "A Node-Based ILP Formulation for the Node-Weighted Dominating Steiner Problem"
"description" => "BLEY, A., LJUBIC, I. et MAURER, O. (2017). A Node-Based ILP Formulation for the Node-Weighted Dominating Steiner Problem. <i>Networks</i>, 69(1), pp. 33-51."
"authors" => array:3 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "BLEY A."
]
2 => array:1 [
"name" => "MAURER O."
]
]
"ouvrage" => ""
"keywords" => array:6 [
0 => "Connected dominating set"
1 => "Steiner tree"
2 => "Integer programming"
3 => "Thin formulation"
4 => "Polyhedron"
5 => "Facets"
]
"updatedAt" => "2021-09-24 10:33:27"
"publicationUrl" => "https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21722"
"publicationInfo" => array:3 [
"pages" => "33-51"
"volume" => "69"
"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" => "In this article, we consider the Node-Weighted Dominating Steiner Problem. Given a graph with node weights and a set of terminal nodes, the goal is to find a connected node-induced subgraph of minimum weight, such that each terminal node is contained in or adjacent to some node in the chosen subgraph. The problem arises in applications in the design of telecommunication networks. Integer programming formulations for Steiner problems usually employ a variable for each edge. We introduce a formulation that only uses node variables and that models connectivity through node-cut inequalities, which can be separated in polynomial time. We discuss necessary and sufficient conditions for the model inequalities to define facets and we introduce a class of lifted partition-based inequalities, which can be used to strengthen the linear relaxation. Finally, we show that the polyhedron defined by these inequalities is integral if the underlying graph is a cycle where no two terminals are adjacent. In the general cycle setting, we show that we can get a complete description of the feasible solutions by lifting and projecting into a polytope with no more than twice the dimension. We also show that the well-known indegree equalities are implied by the lifted partition inequalities. Finally, we evaluate the effectiveness of the presented partition inequalities in computational experiments."
"en" => "In this article, we consider the Node-Weighted Dominating Steiner Problem. Given a graph with node weights and a set of terminal nodes, the goal is to find a connected node-induced subgraph of minimum weight, such that each terminal node is contained in or adjacent to some node in the chosen subgraph. The problem arises in applications in the design of telecommunication networks. Integer programming formulations for Steiner problems usually employ a variable for each edge. We introduce a formulation that only uses node variables and that models connectivity through node-cut inequalities, which can be separated in polynomial time. We discuss necessary and sufficient conditions for the model inequalities to define facets and we introduce a class of lifted partition-based inequalities, which can be used to strengthen the linear relaxation. Finally, we show that the polyhedron defined by these inequalities is integral if the underlying graph is a cycle where no two terminals are adjacent. In the general cycle setting, we show that we can get a complete description of the feasible solutions by lifting and projecting into a polytope with no more than twice the dimension. We also show that the well-known indegree equalities are implied by the lifted partition inequalities. Finally, we evaluate the effectiveness of the presented partition inequalities in computational experiments."
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2024-11-21T11:21:49.000Z"
"docTitle" => "A Node-Based ILP Formulation for the Node-Weighted Dominating Steiner Problem"
"docSurtitle" => "Journal articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, BLEY A., MAURER O."
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, BLEY A., MAURER O.</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2017</span>"
"keywordList" => "<a href="#">Connected dominating set</a>, <a href="#">Steiner tree</a>, <a href="#">Integer programming</a>, <a href="#">Thin formulation</a>, <a href="#">Polyhedron</a>, <a href="#">Facets</a>"
"docPreview" => "<b>A Node-Based ILP Formulation for the Node-Weighted Dominating Steiner Problem</b><br><span>2017-01 | Journal articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21722" target="_blank">A Node-Based ILP Formulation for the Node-Weighted Dominating Steiner Problem</a>"
]
+lang: "en"
+"_type": "_doc"
+"_score": 8.953466
+"parent": null
}
