Article ID: | iaor20021948 |
Country: | Netherlands |
Volume: | 134 |
Issue: | 2 |
Start Page Number: | 439 |
End Page Number: | 456 |
Publication Date: | Oct 2001 |
Journal: | European Journal of Operational Research |
Authors: | Kubat Peter, Smith J. MacGregor |
Keywords: | heuristics |
Mathematical Programming models for multi-period network design problems, which arise in cellular telecommunication systems are presented. The underlying network topologies range from a simple star to complex multi-layer Steiner-like networks. Linear programming, Lagrangian relaxation, and branch-and-cut heuristics are proposed and a polynomial-bounded heuristic based on an interior point linear programming implementation is described. Extensive computational results are presented on a number of randomly generated problem sets and the performance of the heuristic(s) is compared with an optimal branch-and-bound algorithm.