LOWER BOUNDING PROCEDURES FOR MULTIPERIOD TELECOMMUNICATIONS NETWORK EXPANSION PROBLEMS
成果类型：
Article
署名作者：
CHANG, SG; GAVISH, B
署名单位：
Vanderbilt University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.43.1.43
发表日期：
1995
页码：
43-57
关键词：
摘要：
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.