A branch‐and‐price algorithm for the single‐path virtual network embedding problem. Issue 3 (18th December 2017)

• Record Type: Journal Article
• Authors: Moura, Leonardo F.S.; Gaspary, Luciano P.; Buriol, Luciana S.
• Is Part Of: Networks. Volume 71:Issue 3(2018)
• Page Start: 188
• Page End: 208
• Publication Date: 2017-12-18
• Subjects: branch‐and‐price -- column generation -- combinatorial optimization -- exact solution -- integer linear programming -- virtual network embedding; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21798
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : Network virtualization is a growing trend in the implementation of Internet infrastructures. The Virtual Network Embedding problem is one of the challenges in the virtualization of physical networks. This work shows that finding a feasible solution to this problem is NP‐Hard. However, in practice, it can be solved to optimality by exploiting the problem structure. We propose a new branch‐and‐price algorithm applied to a flow‐based formulation of the problem, and present an extensive computational study performed for instances of distinct topologies and sizes. The results presented attest the efficiency of the branch‐and‐price algorithm in solving the problem.