A direct cycle-based column-and-cut generation method for capacitated survivable network design

A direct cycle-based column-and-cut generation method for capacitated survivable network design

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

Reviews

Required fields are marked *. Your email address will not be published.