James (Jim) Luedtke, Assistant Professor: Branch-and-cut approaches for chance-constrained formulations of reliable network design problems
Room:
Wisconsin Institute for Discovery (WID), Room 3280b, (3rd floor teaching lab). Anyone without WID access can use the special events elevator on the WID 1st floor (near ALDOS Café to access 3280b.
Speaker Name:
James (Jim) Luedtke, Assistant Professor
Speaker Institution:
Industrial and Systems Engineering, UW-Madison 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 that demonstrate that the approaches can solve large instances.
This is joint work with Yongjia Song.
Event Date: