Essec\Faculty\Model\Contribution {#2233 ▼
#_index: "academ_contributions"
#_id: "1161"
#_source: array:26 [
"id" => "1161"
"slug" => "1161-exact-approaches-for-network-design-problem-with-relays"
"yearMonth" => "2020-03"
"year" => "2020"
"title" => "Exact Approaches for Network Design Problem with Relays"
"description" => "LEITNER, M., LJUBIC, I., RIEDLER, M. et RUTHMAIR, M. (2020). Exact Approaches for Network Design Problem with Relays. <i>Omega</i>, 91. 
LEITNER, M., LJUBIC, I., RIEDLER, M. et RUTHMAIR, M. (2020). Exact Approaches for Network Design Pro "
"authors" => array:4 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "LEITNER Markus"
]
2 => array:1 [
"name" => "RIEDLER Martin"
]
3 => array:1 [
"name" => "RUTHMAIR Mario"
]
]
"ouvrage" => ""
"keywords" => array:4 [
0 => "Integer programming"
1 => "Networks"
2 => "Layered graphs"
3 => "Telecommunications"
]
"updatedAt" => "2021-09-24 10:33:27"
"publicationUrl" => "https://www.sciencedirect.com/science/article/abs/pii/S030504831830183X"
"publicationInfo" => array:3 [
"pages" => null
"volume" => "91"
"number" => null
]
"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 study the directed network design problem with relays (DNDPR) whose aim is to construct a minimum cost network that enables the communication of a given set of origin-destination pairs. Thereby, expensive signal regeneration devices need to be placed to cover communication distances exceeding a predefined threshold. Applications of the DNDPR arise in telecommunications and transportation. We propose two new integer programming formulations for the DNDPR. The first one is a flow-based formulation with a pseudo-polynomial number of variables and constraints and the second is a cut-based formulation with an exponential number of constraints. Fractional distance values are handled efficiently by augmenting both models with an exponentially-sized set of infeasible path constraints. We develop branch-and-cut algorithms and also consider valid inequalities to strengthen the obtained dual bounds and to speed up convergence. The results of our extensive computational study on diverse sets of benchmark instances show that our algorithms outperform the previous state-of-the-art method based on column generation. We study the directed network design problem with relays (DNDPR) whose aim is to construct a minimum "
"en" => "We study the directed network design problem with relays (DNDPR) whose aim is to construct a minimum cost network that enables the communication of a given set of origin-destination pairs. Thereby, expensive signal regeneration devices need to be placed to cover communication distances exceeding a predefined threshold. Applications of the DNDPR arise in telecommunications and transportation. We propose two new integer programming formulations for the DNDPR. The first one is a flow-based formulation with a pseudo-polynomial number of variables and constraints and the second is a cut-based formulation with an exponential number of constraints. Fractional distance values are handled efficiently by augmenting both models with an exponentially-sized set of infeasible path constraints. We develop branch-and-cut algorithms and also consider valid inequalities to strengthen the obtained dual bounds and to speed up convergence. The results of our extensive computational study on diverse sets of benchmark instances show that our algorithms outperform the previous state-of-the-art method based on column generation. We study the directed network design problem with relays (DNDPR) whose aim is to construct a minimum "
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2025-04-02T11:21:48.000Z"
"docTitle" => "Exact Approaches for Network Design Problem with Relays"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, LEITNER Markus, RIEDLER Martin, RUTHMAIR Mario"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, LEITNER Markus, RIEDLER Martin, RUTHMAIR Mario</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2020</span> <span class="document-property-authors">LJUBIC Ivana, LEITNER Markus, RIEDLER Martin, RUTHMAIR Mario "
"keywordList" => "<a href="#">Integer programming</a>, <a href="#">Networks</a>, <a href="#">Layered graphs</a>, <a href="#">Telecommunications</a> <a href="#">Integer programming</a>, <a href="#">Networks</a>, <a href="#">Layered graphs</a>, <a hr "
"docPreview" => "<b>Exact Approaches for Network Design Problem with Relays</b><br><span>2020-03 | Articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://www.sciencedirect.com/science/article/abs/pii/S030504831830183X" target="_blank">Exact Approaches for Network Design Problem with Relays</a> <a href="https://www.sciencedirect.com/science/article/abs/pii/S030504831830183X" target="_blank">Ex "
]
+lang: "fr"
+"_type": "_doc"
+"_score": 9.282722
+"parent": null
}
