Decomposition algorithms for computational stochastic mixed-integer programming: A survey

The goal of this survey is to provide a road-map for exploring the growing area of stochastic mixed-integer programming (SMIP) models and algorithms. The growth in this area has been phenomenal. As a result, we restrict our exploration to methods which involve stochastic extensions of deterministic integer programs whose applications have appeared over many decades. In this sense, our survey demonstrates the connections between deterministic and stochastic formulations of mixed-integer programming. We provide an overview of existing decomposition algorithms for two-stage SMIPs, including Dantzig–Wolfe decomposition, dual decomposition, as well as strengthening SMIP formulations using Lagrangian cuts, as well as decomposition approaches using parametric cutting planes and scaled cuts. Moreover, we explicitly discuss the relationships among these methods. Furthermore, building on these two-stage results, we summarize recent developments in the emerging field of multistage stochastic mixed-integer programming. Finally, we present directions for future research.