Stochastic Dual Dynamic Programming and Its Variants: A Review

We provide a tutorial-style review of stochastic dual dynamic programming (SDDP), one of the state-of-the-art solution methods for large-scale multistage stochastic programs. Since it was introduced about 30 years ago for solving large-scale multistage stochastic linear programming problems in energy planning, SDDP has been applied to practical problems from several fields and has been enriched by various improvements and enhancements to address broader problem classes. We begin with a detailed introduction to SDDP, with special focus on its motivation, complexity, and required assumptions. Then, we present and discuss in depth the existing enhancements as well as current research trends that allow for the alleviation of those assumptions.