A DECOMPOSITION ALGORITHM FOR LOCAL ACCESS TELECOMMUNICATIONS NETWORKEXPANSION PLANNING

Growing demand, increasing diversity of services, and advances in tran smission and switching technologies are prompting telecommunication co mpanies to rapidly expand and modernize their networks. This paper dev elops and tests a decomposition methodology to generate cost-effective expansion plans, with performance guarantees, for one major component of the network hierarchy-the local access network. The model captures economies of scale in facility costs and tradeoffs between installing concentrators and expanding cables to accommodate demand growth. Our solution method exploits the special tree and routing structure of the expansion planning problem to incorporate valid inequalities, obtaine d by studying the problem's polyhedral structure, in a dynamic program which solves an uncapacitated version of the problem. Computational r esults for three realistic rest networks demonstrate that our enhanced dynamic programming algorithm, when embedded in a Lagrangian relaxati on scheme (with problem preprocessing and Ideal improvement), Is very effective in generating good upper and lower bound;: Implemented on a personal computer, the method generates solutions within 1.2-7.0% of o ptimality. In addition to developing a successful solution methodology for a practical problem, this paper illustrates the possibility of ef fectively combining decomposition methods and polyhedral approaches.