Benders decomposition for a node-capacitated Virtual Network Function placement and routing problem

In this paper we study a problem faced by network service providers in which a set of Virtual Network Functions (VNFs) has to be installed in a telecommunication network at minimum cost. For each given origin-destination pair of nodes (commodities), a latency-constrained routing path has to be found that visits the required VNFs in a pre-defined order. A limited number of functions can be installed at each node. We first prove that the problem is NP-hard in a strong sense, even for a single commodity and without node-capacity, latency and precedence constraints. We then provide a compact Mixed Integer Linear Programming (MILP) formulation, along with several families of valid inequalities. To tackle the problem from a computational perspective, we provide theoretical results that allow us to derive Benders reformulation of the problem. We also exploit an alternative path-based MILP formulation to derive heuristic solutions. All these ingredients are combined in a Branch-and-Benders-Cut framework and computationally tested on a wide range of realistic instances. Our results are also compared with the Automatic Benders decomposition provided by Cplex. Computational results indicate that our decomposition approach is more efficient compared to the two methods provided by the off-the-shelf solver, both in terms of the CPU time and the overall solution quality. The results also indicate that our MILP-heuristic provides high-quality solutions.