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

Manish Garg, J. Cole Smith

Research output: Contribution to journalArticle

43 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1057-1071
Number of pages15
JournalOmega
Volume36
Issue number6
DOIs
StatePublished - Dec 1 2008
Externally publishedYes

Keywords

  • Computing
  • Integer programming
  • Optimization
  • Routing

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios'. Together they form a unique fingerprint.

  • Cite this