A directed cycle-based column-and-cut generation method for capacitated survivable network design
✍ Scribed by Deepak Rajan; Alper Atamtürk
- Publisher
- John Wiley and Sons
- Year
- 2004
- Tongue
- English
- Weight
- 157 KB
- Volume
- 43
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
A network is said to be survivable if it has sufficient capacity for rerouting all of its flow under the failure of any one of its edges. Here, we present a polyhedral approach for designing survivable networks. We describe a mixed‐integer programming model, in which sufficient slack is explicitly introduced on the directed cycles of the network while flow routing decisions are made. In case of a failure, flow is rerouted along the slacks reserved on directed cycles. We give strong valid inequalities that use the survivability requirements. We present a computational study with a column‐and‐cut generation algorithm for designing capacitated survivable networks. © 2004 Wiley Periodicals, Inc.