Article ID: | iaor20043731 |
Country: | Netherlands |
Volume: | 43 |
Issue: | 4 |
Start Page Number: | 201 |
End Page Number: | 211 |
Publication Date: | Apr 2004 |
Journal: | Networks |
Authors: | Atamtrk Alper, Rajan Deepak |
Keywords: | networks: flow, programming: integer |
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