Modeling and Solving the Two-Facility Capacitated Network Loading Problem

This paper studies a topical and economically significant capacitated network design problem that arises in the telecommunications industry. In this problem, given point-to-point communication demand in a network must be met by installing (loading) capacitated facilities on the arcs: Loading a facility incurs an arc specific and facility dependent cost. This paper develops modeling and solution approaches for loading facilities to satisfy the given demand at minimum cost. We consider two approaches for solving the underlying mixed integer program: a Lagrangian relaxation strategy, and a cutting plane approach that uses three classes of valid inequalities that we identify for the problem. We show that a linear programming formulation that includes these inequalities always approximates the value of the mixed integer program at least as well as the Lagrangian relaxation bound. Our computational results on a set of prototypical telecommunication data show that including these inequalities considerably improves the gap between the integer programming formulation and its linear programming relaxation: from an average of 25% to an average of 8%. These results show that strong cutting planes can be an effective modeling and algorithmic tool for solving problems of the size that arise in the telecommunications industry.