A Polyhedral Approach to Multicommodity Survivable Network Design.
Please always quote using this URN: urn:nbn:de:0297-zib-1162
- 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 non-redundant inequalities for the polyhedron of capacity design variables, by exploiting its relationship to connectivity network design and knapsack-like subproblems. Computational work using this model and the additional inequalities is in progress.
Author: | Mechthild Stoer, Geir Dahl |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1993/09/06 |
Series (Serial Number): | ZIB-Report (SC-93-20) |
ZIB-Reportnumber: | SC-93-20 |
Published in: | Appeared in: Numerische Mathematik 68 (1994), pp. 149-167 |