Model and heuristic for a generalized access network design problem

The generalized access network design problem consists of finding a topology, capacity assignment and routing that minimize the sum of costs to connect every pair of remote unit and its central node specified by the telecommunication company. We consider an integer programming formulation with a partial multicommodity structure. We analyze some aspects and extensions of the proposed model and we introduce a heuristic based on Lagrangian relaxation and the subgradient method. We report computational results for a set of randomly generated test problems. They include networks with up to 300 nodes and show that even problem instances defined in small networks can be extremely difficult problems. The heuristic generates effective and acceptable designs from the practical point of view. We compare our heuristic with a commercial code. This revised version was published online in June 2006 with corrections to the Cover Date.