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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Methods for Multistage Stochastic Linear Programs

  • Wim Stefanus van Ackooij,
  • Welington Luis de Oliveira

摘要

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.