Optimization Online


Branch-and-cut Approaches for Chance-constrained Formulations of Reliable Network Design Problems

Yongjia Song (ysong29***at***wisc.edu)
James Luedtke (jrluedt1***at***wisc.edu)

Abstract: We study solution approaches for the design of reliably connected networks. Speci fically, given a network with arcs that may fail at random, the goal is to select a minimum cost subset of arcs such the probability that a connectivity requirement is satis ed is at least 1-\epsilon, where \epsilon is a risk tolerance. We consider two types of connectivity requirements. We first study the problem of requiring an s-t path to exist with high probability in a directed graph. Then we consider undirected graphs, where we require the graph to be fully connected with high probability. We model each problem as a stochastic integer program with a joint chance constraint, and present two formulations that can be solved by a branch-and-cut algorithm. The fi rst formulation uses binary variables to represent whether or not the connectivity requirement is satis ed in each scenario of arc failures and is based on inequalities derived from graph cuts in individual scenarios. We derive additional valid inequalities for this formulation and study their facet-inducing properties. The second formulation is based on probabilistic graph cuts, an extension of graph cuts to graphs with random arc failures. Inequalities corresponding to probabilistic graph cuts are sufficient to defi ne the set of feasible solutions and can be separated efficiently at integer solutions, allowing this formulation to be solved by a branch-and-cut algorithm. Computational results demonstrate that the approaches can e ffectively solve instances on large graphs with many failure scenarios. In addition, we demonstrate that, by varying the risk tolerance, our model yields a rich set of solutions on the efficient frontier of cost and reliability.

Keywords: Reliable network design, chance constraints, integer programming

Category 1: Stochastic Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )


Download: [PDF]

Entry Submitted: 09/27/2011
Entry Accepted: 09/27/2011
Entry Last Modified: 08/09/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society