Essec\Faculty\Model\Contribution {#2233
#_index: "academ_contributions"
#_id: "13966"
#_source: array:26 [
"id" => "13966"
"slug" => "two-extended-formulations-for-the-virtual-network-function-placement-and-routing-problem"
"yearMonth" => "2023-07"
"year" => "2023"
"title" => "Two extended formulations for the virtual network function placement and routing problem"
"description" => "MOUACI, A., GOURDIN, , LJUBIC, I. et PERROT, N. (2023). Two extended formulations for the virtual network function placement and routing problem. <i>Networks</i>, 82(1), pp. 32-51."
"authors" => array:4 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "MOUACI Ahlam"
]
2 => array:1 [
"name" => "GOURDIN Éric"
]
3 => array:1 [
"name" => "PERROT Nancy"
]
]
"ouvrage" => ""
"keywords" => array:5 [
0 => "branch-and-price"
1 => "column generation"
2 => "network function virtualization"
3 => " networks"
4 => "service functions chaining"
]
"updatedAt" => "2024-10-31 13:51:19"
"publicationUrl" => "https://doi.org/10.1002/net.22144"
"publicationInfo" => array:3 [
"pages" => "32-51"
"volume" => "82"
"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" => "Given a bi-directed graph modeling a telecommunication network, and a set of origin-destination pairs representing traffic requests (commodities) along with their associated Service Function Chains (SFCs), the Virtual Network Function Placement and Routing Problem (VNFPRP) aims to find, for each commodity, one latency-constrained routing path that visits the required Virtual Network Functions in a specific order. The function installation costs together with the node activation costs have to be minimized. In this paper, we present two extended Mixed Integer Programming (MIP) formulations to model the VNFPRP. For each formulation we define the master problem, the pricing problem, the associated Lagrangian bound and a specific branching scheme, in order to derive an efficient Branch-and-Price algorithm. We also provide several families of valid inequalities to strengthen the LP-relaxation bounds. Computational results are reported comparing the performance of the two Branch-and-Price algorithms with a compact MIP formulation and its Branch-and-Benders-cut implementation on a set of SNDlib instances representing telecommunication networks."
"en" => "Given a bi-directed graph modeling a telecommunication network, and a set of origin-destination pairs representing traffic requests (commodities) along with their associated Service Function Chains (SFCs), the Virtual Network Function Placement and Routing Problem (VNFPRP) aims to find, for each commodity, one latency-constrained routing path that visits the required Virtual Network Functions in a specific order. The function installation costs together with the node activation costs have to be minimized. In this paper, we present two extended Mixed Integer Programming (MIP) formulations to model the VNFPRP. For each formulation we define the master problem, the pricing problem, the associated Lagrangian bound and a specific branching scheme, in order to derive an efficient Branch-and-Price algorithm. We also provide several families of valid inequalities to strengthen the LP-relaxation bounds. Computational results are reported comparing the performance of the two Branch-and-Price algorithms with a compact MIP formulation and its Branch-and-Benders-cut implementation on a set of SNDlib instances representing telecommunication networks."
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2024-12-13T15:21:45.000Z"
"docTitle" => "Two extended formulations for the virtual network function placement and routing problem"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, MOUACI Ahlam, GOURDIN Éric, PERROT Nancy"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, MOUACI Ahlam, GOURDIN Éric, PERROT Nancy</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2023</span>"
"keywordList" => "<a href="#">branch-and-price</a>, <a href="#">column generation</a>, <a href="#">network function virtualization</a>, <a href="#"> networks</a>, <a href="#">service functions chaining</a>"
"docPreview" => "<b>Two extended formulations for the virtual network function placement and routing problem</b><br><span>2023-07 | Articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://doi.org/10.1002/net.22144" target="_blank">Two extended formulations for the virtual network function placement and routing problem</a>"
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.59593
+"parent": null
}