A branch-and-price algorithm for the single-path virtual network embedding problem

作者：Moura Leonardo F. S.; Gaspary Luciano P.; Buriol Luciana S.^*

来源：Networks, 2018, 71(3): 188-208.

DOI：10.1002/net.21798

• branch-and-price
• column generation
• combinatorial optimization
• exact solution
• integer linear programming
• virtual network embedding

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.

• 出版日期2018-4