TY - JOUR

T1 - Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios

AU - Garg, Manish

AU - Smith, J. Cole

N1 - Funding Information:
We are grateful for the comments of three anonymous referees and of an Associate Editor, which led to an improved presentation of our work. This material is based upon work supported by the Defense Advanced Research Projects Agency under Grant number N66001-01-1-8925.

PY - 2008/12

Y1 - 2008/12

N2 - We consider the design of a multicommodity flow network, in which point-to-point demands are routed across the network subject to link capacity restrictions. Such a design must build enough capacity and diverse routing paths through the network to ensure that feasible multicommodity flows continue to exist, even when components of the network fail. In this paper, we examine several methodologies to optimally design a minimum-cost survivable network that continues to support a multicommodity flow under any of a given set of failure scenarios, where each failure scenario consists of the simultaneous failure of multiple arcs. We begin by providing a single extensive form mixed-integer programming formulation for this problem, along with a Benders decomposition algorithm as an alternative to the extensive form approach. We next investigate strategies to improve the performance of the algorithm by augmenting the master problem with several valid inequalities such as cover constraints, connectivity constraints, and path constraints. For the smallest instances (eight nodes, 10 origin-destination pairs, and 10 failure scenarios), the Benders implementation consumes only 10% of the time required by the mixed-integer programming formulation, and our best augmentation strategy reduces the solution time by another 50%. For medium- and large-sized instances, the extensive form problem fails to terminate within 2 h on any instance, while our decomposition algorithms provide optimal solutions on all but two problem instances.

AB - We consider the design of a multicommodity flow network, in which point-to-point demands are routed across the network subject to link capacity restrictions. Such a design must build enough capacity and diverse routing paths through the network to ensure that feasible multicommodity flows continue to exist, even when components of the network fail. In this paper, we examine several methodologies to optimally design a minimum-cost survivable network that continues to support a multicommodity flow under any of a given set of failure scenarios, where each failure scenario consists of the simultaneous failure of multiple arcs. We begin by providing a single extensive form mixed-integer programming formulation for this problem, along with a Benders decomposition algorithm as an alternative to the extensive form approach. We next investigate strategies to improve the performance of the algorithm by augmenting the master problem with several valid inequalities such as cover constraints, connectivity constraints, and path constraints. For the smallest instances (eight nodes, 10 origin-destination pairs, and 10 failure scenarios), the Benders implementation consumes only 10% of the time required by the mixed-integer programming formulation, and our best augmentation strategy reduces the solution time by another 50%. For medium- and large-sized instances, the extensive form problem fails to terminate within 2 h on any instance, while our decomposition algorithms provide optimal solutions on all but two problem instances.

KW - Computing

KW - Integer programming

KW - Optimization

KW - Routing

UR - http://www.scopus.com/inward/record.url?scp=40649102942&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=40649102942&partnerID=8YFLogxK

U2 - 10.1016/j.omega.2006.05.006

DO - 10.1016/j.omega.2006.05.006

M3 - Article

AN - SCOPUS:40649102942

VL - 36

SP - 1057

EP - 1071

JO - Omega

JF - Omega

SN - 0305-0483

IS - 6

ER -