A new effective mathematical programming model to design CDN topology

Abstract

The Steiner Tree Problem is an umbrella of combinatorial optimization problems in graphs, most of them NP-Hard, within which, the Steiner Tree Problem in graphs (STP) is perhaps one of the most famous and widely studied. The STP consists in optimally interconnect a given set of terminal or mandatory nodes within a graph with edges of positive weights, eventually using other optional nodes. It has a wide range of applications from circuit layouts to network design, so plenty of models to find its exact solutions have been crafted. Traditionally, due to its intrinsic complexity, heuristic approaches have been used to find good quality solutions to the STP. Currently, the outstanding computing power resulting from combining developments in hardware and software capabilities makes it possible to rely upon exact formulations and generic algorithms to solve complex instances of the problem. This work introduces a flow-based mixed-integer problem formulation (MIP) for the STP using the SteinLib, a reference test-set repository. Later on, that MIP formulation is modified to solve the Quality of Service Multicast Tree problem (QoSTP). To the best of our knowledge, there is no previous MIP formulation. While existing approaches go all the way of approximation algorithms to find solutions, this MIP formulation shows promising experimental results. Optimal solutions are found for several instances, while low feasible-to-optimal gaps were obtained for most of the remaining ones.