Lower bounding procedures for multiperiod telecommunications network expansion problems

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.