  


Branchandcut Approaches for Chanceconstrained Formulations of Reliable Network Design Problems
Yongjia Song (ysong29wisc.edu) Abstract: We study solution approaches for the design of reliably connected networks. Specifically, 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 satised 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 st 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 branchandcut algorithm. The first formulation uses binary variables to represent whether or not the connectivity requirement is satised 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 facetinducing 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 define the set of feasible solutions and can be separated efficiently at integer solutions, allowing this formulation to be solved by a branchandcut algorithm. Computational results demonstrate that the approaches can effectively 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 ) Citation: Download: [PDF] Entry Submitted: 09/27/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  