Sampling-based Decomposition Algorithms for Multistage Stochastic Programming

Sampling-based algorithms provide a practical approach to solving large-scale multistage stochastic programs. This chapter presents two alternative approaches to incorporating sampling within multistage stochastic linear programming algorithms. In the first approach, sampling is used to construct a sample average approximation (SAA) of the true multistage program. Subsequently, an optimization step is undertaken using deterministic decomposition methods that utilize randomization. A comparison of various algorithms that adopt this approach, including stochastic dual dynamic programming, is provided. In the second stochastic decomposition approach, sampling and optimization are carried out concurrently. In stochastic dynamic linear programming, an example of the second approach, the representation of uncertainty is refined in every iteration of the algorithm. The differences in how the approximations of the cost-to-go functions are constructed under these alternative approaches are illustrated.

Article

Download

View Sampling-based Decomposition Algorithms for Multistage Stochastic Programming