Two extended formulations for the virtual network function placement and routing problem

Given a bi-directed graph modeling a telecommunication network, and a set of origin-destination pairs representing traffic requests (commodities) along with their associated Service Function Chains (SFCs), the Virtual Network Function Placement and Routing Problem (VNFPRP) aims to find, for each commodity, one latency-constrained routing path that visits the required Virtual Network Functions in a specific order. The function installation costs together with the node activation costs have to be minimized. In this paper, we present two extended Mixed Integer Programming (MIP) formulations to model the VNFPRP. For each formulation we define the master problem, the pricing problem, the associated Lagrangian bound and a specific branching scheme, in order to derive an efficient Branch-and-Price algorithm. We also provide several families of valid inequalities to strengthen the LP-relaxation bounds. Computational results are reported comparing the performance of the two Branch-and-Price algorithms with a compact MIP formulation and its Branch-and-Benders-cut implementation on a set of SNDlib instances representing telecommunication networks.