Essec\Faculty\Model\Contribution {#2233
#_index: "academ_contributions"
#_id: "12599"
#_source: array:26 [
"id" => "12599"
"slug" => "benders-decomposition-for-a-node-capacitated-virtual-network-function-placement-and-routing-problem"
"yearMonth" => "2021-06"
"year" => "2021"
"title" => "Benders decomposition for a node-capacitated Virtual Network Function placement and routing problem"
"description" => "LJUBIC, I., MOUACI, A., PERROT, N. et GOURDIN, E. (2021). Benders decomposition for a node-capacitated Virtual Network Function placement and routing problem. <i>Computers & Operations Research</i>, 130(105227)."
"authors" => array:4 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "MOUACI Ahlam"
]
2 => array:1 [
"name" => "PERROT Nancy"
]
3 => array:1 [
"name" => "GOURDIN Eric"
]
]
"ouvrage" => ""
"keywords" => array:6 [
0 => "Combinatorial optimization"
1 => "Benders decomposition"
2 => "Software defined networking"
3 => "Network Function"
4 => "Virtualization"
5 => "Service function chaining"
]
"updatedAt" => "2021-09-24 10:33:27"
"publicationUrl" => "https://doi.org/10.1016/j.cor.2021.105227"
"publicationInfo" => array:3 [
"pages" => null
"volume" => "130"
"number" => "105227"
]
"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 paper we study a problem faced by network service providers in which a set of Virtual Network Functions (VNFs) has to be installed in a telecommunication network at minimum cost. For each given origin-destination pair of nodes (commodities), a latency-constrained routing path has to be found that visits the required VNFs in a pre-defined order. A limited number of functions can be installed at each node. We first prove that the problem is NP-hard in a strong sense, even for a single commodity and without node-capacity, latency and precedence constraints. We then provide a compact Mixed Integer Linear Programming (MILP) formulation, along with several families of valid inequalities. To tackle the problem from a computational perspective, we provide theoretical results that allow us to derive Benders reformulation of the problem. We also exploit an alternative path-based MILP formulation to derive heuristic solutions. All these ingredients are combined in a Branch-and-Benders-Cut framework and computationally tested on a wide range of realistic instances. Our results are also compared with the Automatic Benders decomposition provided by Cplex. Computational results indicate that our decomposition approach is more efficient compared to the two methods provided by the off-the-shelf solver, both in terms of the CPU time and the overall solution quality. The results also indicate that our MILP-heuristic provides high-quality solutions."
"en" => "In this paper we study a problem faced by network service providers in which a set of Virtual Network Functions (VNFs) has to be installed in a telecommunication network at minimum cost. For each given origin-destination pair of nodes (commodities), a latency-constrained routing path has to be found that visits the required VNFs in a pre-defined order. A limited number of functions can be installed at each node. We first prove that the problem is NP-hard in a strong sense, even for a single commodity and without node-capacity, latency and precedence constraints. We then provide a compact Mixed Integer Linear Programming (MILP) formulation, along with several families of valid inequalities. To tackle the problem from a computational perspective, we provide theoretical results that allow us to derive Benders reformulation of the problem. We also exploit an alternative path-based MILP formulation to derive heuristic solutions. All these ingredients are combined in a Branch-and-Benders-Cut framework and computationally tested on a wide range of realistic instances. Our results are also compared with the Automatic Benders decomposition provided by Cplex. Computational results indicate that our decomposition approach is more efficient compared to the two methods provided by the off-the-shelf solver, both in terms of the CPU time and the overall solution quality. The results also indicate that our MILP-heuristic provides high-quality solutions."
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2024-11-21T13:21:44.000Z"
"docTitle" => "Benders decomposition for a node-capacitated Virtual Network Function placement and routing problem"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, MOUACI Ahlam, PERROT Nancy, GOURDIN Eric"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, MOUACI Ahlam, PERROT Nancy, GOURDIN Eric</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2021</span>"
"keywordList" => "<a href="#">Combinatorial optimization</a>, <a href="#">Benders decomposition</a>, <a href="#">Software defined networking</a>, <a href="#">Network Function</a>, <a href="#">Virtualization</a>, <a href="#">Service function chaining</a>"
"docPreview" => "<b>Benders decomposition for a node-capacitated Virtual Network Function placement and routing problem</b><br><span>2021-06 | Articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://doi.org/10.1016/j.cor.2021.105227" target="_blank">Benders decomposition for a node-capacitated Virtual Network Function placement and routing problem</a>"
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.760923
+"parent": null
}
