LOWER BOUNDING PROCEDURES FOR MULTIPERIOD TELECOMMUNICATIONS NETWORK EXPANSION PROBLEMS

This paper suggests an improved formulation for the multiperiod networ k topology and capacity expansion problem and proposes new lower bound ing schemes based on it. It differs from earlier formulations and solu tion methods in that entirely new and different subproblems are solved and a number of lower bound tightening schemes are added within the f ramework of a Lagrangian relaxation. Dual ascent and multiplier adjust ment procedures are suggested for the Lagrange multiplier updating pro cedure. Computational results are reported to demonstrate the tightnes s of the bounds generated by the suggested procedures. Heuristics base d on converting the dual information obtained from the Lagrangian proc edure into primal feasible solutions are tested. The tests show that t he Lagrangian-based heuristics generate solutions superior to solution s generated by other heuristics proposed in the literature.