Summary.
The design of cost-efficient networks satisfying certain survivability constraints is of major concern to the telecommunications industry. In this paper we study a problem of extending the capacity of a network by discrete steps as cheaply as possible, such that the given traffic demand can be accommodated even when a single edge or node in the network fails. We derive valid and nonredundant inequalities for the polyhedron of capacity design variables, by exploiting its relationship to connectivity network design and knapsack-like subproblems. A cutting plane algorithm and heuristics for the problem are described, and preliminary computational results are reported.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received August 26, 1993 / Revised version received February 1994
Rights and permissions
About this article
Cite this article
Stoer, M., Dahl, G. A polyhedral approach to multicommodity survivable network design . Numer. Math. 68, 149–167 (1994). https://doi.org/10.1007/s002110050054
Issue Date:
DOI: https://doi.org/10.1007/s002110050054