A polyhedral approach tomulticommodity survivable network design |
| |
Authors: | Mechthild Stoer Geir Dahl |
| |
Affiliation: | (1) Konrad-Zuse-Zentrum f"ur Informationstechnik Berlin, Heilbronner Strasse 10, D-10711 Berlin, Germany E-mail: stoer{tt @}zib-berlin.de , DE;(2) Norwegian Telecom Research, P.O.Box 83, N-2007 Kjeller, Norway E-mail: geir.dahl{tt @}tf.tele.no , NO |
| |
Abstract: | 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. Received August 26, 1993 / Revised version received February 1994 |
| |
Keywords: | Mathematics Subject Classification (1991): 65K05 90C35 |
本文献已被 SpringerLink 等数据库收录! |
|