A branch‐and‐price algorithm for the single‐path virtual network embedding problem
Leonardo Fernando dos Santos Moura, Luciano Paschoal Gaspary, Luciana Salete Buriol · Networks · 2017
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.