A Decomposition Algorithm for Local Access Telecommunications Network Expansion Planning

Anantaram Balakrishnan, Thomas L. Magnanti and Richard T. Wong
Additional contact information
Anantaram Balakrishnan: Massachusetts Institute of Technology, Cambridge, Massachusetts
Thomas L. Magnanti: Massachusetts Institute of Technology, Cambridge, Massachusetts
Richard T. Wong: AT&T Bell Laboratories, Holmdel, New Jersey

Operations Research, 1995, vol. 43, issue 1, 58-76

Abstract: Growing demand, increasing diversity of services, and advances in transmission and switching technologies are prompting telecommunication companies to rapidly expand and modernize their networks. This paper develops 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, obtained by studying the problem’s polyhedral structure, in a dynamic program which solves an uncapacitated version of the problem. Computational results for three realistic test networks demonstrate that our enhanced dynamic programming algorithm, when embedded in a Lagrangian relaxation scheme (with problem preprocessing and local improvement), is very effective in generating good upper and lower bounds: Implemented on a personal computer, the method generates solutions within 1.2–7.0% of optimality. In addition to developing a successful solution methodology for a practical problem, this paper illustrates the possibility of effectively combining decomposition methods and polyhedral approaches.

Keywords: communications: integer programming for local access expansion; networks/graphs; applications: capacity expansion of local access telephone systems; programming; integer; algorithms: expanding local access telephone networks (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.1.58 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:43:y:1995:i:1:p:58-76

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().