Lower Bounding Procedures for Multiperiod Telecommunications Network Expansion Problems

Suk-Gwon Chang and Bezalel Gavish
Additional contact information
Suk-Gwon Chang: Hanyang University, Seoul, Korea
Bezalel Gavish: Vanderbilt University, Nashville, Tennessee

Operations Research, 1995, vol. 43, issue 1, 43-57

Abstract: This paper suggests an improved formulation for the multiperiod network topology and capacity expansion problem and proposes new lower bounding schemes based on it. It differs from earlier formulations and solution methods in that entirely new and different subproblems are solved and a number of lower bound tightening schemes are added within the framework of a Lagrangian relaxation. Dual ascent and multiplier adjustment procedures are suggested for the Lagrange multiplier updating procedure. Computational results are reported to demonstrate the tightness of the bounds generated by the suggested procedures. Heuristics based on converting the dual information obtained from the Lagrangian procedure into primal feasible solutions are tested. The tests show that the Lagrangian-based heuristics generate solutions superior to solutions generated by other heuristics proposed in the literature.

Keywords: facilities/equipment planning: capacity expansion of telecommunications networks; networks/graphs; theory: lower bound for multiperiod network expansion problems; programming; integer; heuristic: dual-based algorithms; lower bounding procedures (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.43.1.43 (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:43-57

Access Statistics for this article

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