Title: Branch-and-cut approaches for chance-constrained formulations of reliable network design problems
Date: April 11, 2013
Location: University of Iowa, Department of Mechanical and Industrial Engineering
Abstract: We study the design of reliably connected networks. Given a graph with arcs that may fail at random, the goal is to select a minimum cost set of arcs such that a connectivity requirement is met with high probability. We first compare this model with a well-known deterministic model of reliable network design: survivable network design. We demonstrate that, if distributional information on arc failures is known, the chance constraint model can yield a significantly richer set of solutions on the efficient frontier of reliability and cost. We then present two solution approaches for our model, which we formulate as a chance-constrained stochastic integer program. The first approach is based on a formulation that uses binary variables to determine if the connectivity requirement is satisfied in each arc failure scenario, and enforces the connectivity requirement in selected scenarios using scenario-based graph cuts. We derive additional classes of valid inequalities for this formulation and study their facet-inducing properties. The second formulation is based on the idea of probabilistic graph cuts, which is an extension of graph cuts to graphs with random arc failures. Inequalities defined by such 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 branch-and-cut algorithm. Computational results will be presented.
This is joint work with Yongjia Song.