Deployment of Mobile Switching Centers in a Telecommunications Network: A Stochastic Programming Approach

We consider a network design problem arising in mobile communications. At the core of the network is a number of mobile switching centers (MSCs), each serving a number of base station controllers (BSCs). The network design problem involves three major groups of decisions – deployment of a number of new MSCs, allocation of BSCs to new and existing MSCs, and capacity expansion of transmission links interconnecting the MSCs. These decisions must be made so as to minimize the incurred costs while meeting customer demand and observing the capacity restrictions. We formulate the problem as a two-stage stochastic program with mixed-integer recourse. To solve the problem we apply a dual decomposition procedure, solving scenario subproblems by means of branch and cut. The solution procedure has been tested on a real life problem instance provided by SONOFON, a Danish mobile communication network operator, and we report results of our computational experiments.