Compact and Extended Formulations for the Virtual Network Embedding Problem

Virtualization allows multiple virtual networks to be nested in a common substrate network sharing resources such as CPU, memory and bandwidth. For that, a Virtual Network Embedding problem needs to be solved, allocating virtual requests to physical components with available capacities. This problem is NP-hard and exact approaches still present many challenges to be tackled. In this work three formulations are compared showing the strengths of the linear programming relaxations. For that, column generation algorithms are devised, indicating optimality may be achieved faster through decomposition approaches.