Benders Decomposition for Solving Two-stage Stochastic Optimization Models
Presenter
August 9, 2016
Keywords:
- Stochastic programming, stochastic optimization, Benders decomposition, L-shaped algorithm
MSC:
- 90C15
Abstract
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.