Branch-and-cut approaches for chance-constrained formulations of reliable network design problems

Jim Luedtke
Assistant Professor, Industrial and Systems Engineering

Date and Time: 

Thursday, November 8, 2012 - 4:00pm

Event Location: 

Mohler Lab Room 451

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.

Bio Sketch: 

Jim Luedtke is an Assistant Professor in the Department of Industrial and Systems Engineering at the University of Wisconsin-Madison. Luedtke earned his Ph.D. at Georgia Tech and did a postdoc at the IBM T.J. Watson Research Center. Luedtke's research lies in the areas of stochastic and mixed-integer programming, with interest in applications in service systems and energy. In stochastic programming, funded by an NSF CAREER award, Luedtke has focused on models and algorithms for risk-constrained optimization. In mixed-integer programming, Luedtke is currently studying mixed-integer nonlinear sets with the goal of finding strong and efficiently solvable convex relaxations.