Premium
A branch‐and‐price algorithm for the single‐path virtual network embedding problem
Author(s) -
Moura Leonardo F.S.,
Gaspary Luciano P.,
Buriol Luciana S.
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21798
Subject(s) - computer science , network virtualization , embedding , virtualization , mathematical optimization , network topology , path (computing) , minimum cost flow problem , virtual network , flow network , algorithm , distributed computing , mathematics , computer network , cloud computing , artificial intelligence , operating system
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.