Article ID: | iaor1999357 |
Country: | United States |
Volume: | 10 |
Issue: | 1 |
Start Page Number: | 1 |
End Page Number: | 11 |
Publication Date: | Dec 1998 |
Journal: | INFORMS Journal On Computing |
Authors: | Stoer Mechthild, Dahl Geir |
Keywords: | optimization, communications |
We present a cutting plane algorithm for solving the following telecommunications network design problem: given point-to-point traffic demands in a network, specified survivability requirements and a discrete cost/capacity function for each link, find minimum cost capacity expansions satisfying the given demands. In this article we describe the underlying problem, the model and the main ingredients in our algorithm. This includes: initial formulation, feasibility test, separation for strong cutting planes, and primal heuristics. Computational results for a set of real-world problems are reported.