Methods for Multistage Stochastic Linear Programs
摘要
Instead of splitting methods that decompose stochastic programs into scenarios, this chapter focuses on node-decomposition approaches for solving multistage stochastic programs. Given a multistage scenario tree, strategies based on node decomposition yield smaller and simpler subproblems, reliable lower bound on the optimal value, and, more importantly, cutting-plane approximations of dynamic functions modelling future random costs. This chapter starts with the well-known nested decomposition (ND), which is an extension of the Benders decomposition to multistage stochastic linear programs. It then passes to a randomized variant of ND, denoted by stochastic dual dynamic programming (SDDP) algorithm. The focus is the linear setting.