Benders Decomposition for Solving Two-stage Stochastic Optimization Models

Tuesday, August 9, 2016 - 9:00am - 10:30am
Lind 305
Jim Luedtke (University of Wisconsin, Madison)
We present the Benders decomposition algorithm for solving two-stage stochastic optimization models. The main feature of this algorithm is that it alternates between solving a relatively compact master problem, and a set of subproblems, one per scenario, which can be solved independently (hence decomposing the large problem into many small problems). After presenting and demonstrating correctness of the basic algorithm, several computational enhancements will be discussed, including effective selection of cuts, multi-cut vs. single-cut approaches, and stabilization techniques.
MSC Code: