MODELING AND SOLVING THE 2-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 netwo rk must be met by installing (loading) capacitated facilities on the a rcs: Loading a facility incurs an are 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 t wo approaches for solving the underlying mixed integer program: Lagran gian relaxation strategy, and a cotting plane approach that uses three classes of valid inequalities that we identify for the problem. We sh ow that a linear programming formulation that includes these inequalit ies always approximates the value of the mixed integer program at leas t as well as the Lagrangian relaxation bound. Our computational result s on a set of prototypical telecommunication data show that including these inequalities considerably improves the gap between the integer p rogramming formulation and its linear programming relaxation: from an average of 25% to an average of 8%. These results show that strong cut ting planes can be an effective modeling and algorithmic tool for solv ing problems of the size that arise in the telecommunications industry .