Telecommunication Link Restoration Planning with Multiple Facility Types

Authors: Anantaram Balakrishnan, Thomas L. Magnanti, Joel S. Sokol, Yi Wang

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network with steady-state working flows to permit link restoration. We present a spare capacity planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances for which the bounds are tight to within a constant factor. In tests on three real-world problems and several randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. For small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, suggesting that the heuristic solutions are closer to optimality than implied by the gaps.