Optimization problems arising from real-life applications are often subject to uncertain data, such as demand, prices, resources, and weather conditions. In general, data evolve over time, and decisions need to be made at different stages before observing the entire data stream. Depending on the application and available data, this class of decision-making problems can be formulated as multistage stochastic programs (MSP). This chapter presents splitting algorithms for solving multistage stochastic programs. The approach is to pose the original MSP as a linkage problem so that the progressive decoupling algorithm of Chap. 9 can be applied, yielding a decomposition per scenario. Alternatively, the multistage optimization problem is posed as one of finding a zero of the sum of two appropriate monotone operators, which is solved by a (randomized) variant of the Douglas-Rachford splitting method. The attractiveness of such algorithms is that they can be easily derived from implementations of deterministic counterparts of the problem.

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

Progressive Decoupling in Multistage Stochastic Programming

  • Wim Stefanus van Ackooij,
  • Welington Luis de Oliveira

摘要

Optimization problems arising from real-life applications are often subject to uncertain data, such as demand, prices, resources, and weather conditions. In general, data evolve over time, and decisions need to be made at different stages before observing the entire data stream. Depending on the application and available data, this class of decision-making problems can be formulated as multistage stochastic programs (MSP). This chapter presents splitting algorithms for solving multistage stochastic programs. The approach is to pose the original MSP as a linkage problem so that the progressive decoupling algorithm of Chap. 9 can be applied, yielding a decomposition per scenario. Alternatively, the multistage optimization problem is posed as one of finding a zero of the sum of two appropriate monotone operators, which is solved by a (randomized) variant of the Douglas-Rachford splitting method. The attractiveness of such algorithms is that they can be easily derived from implementations of deterministic counterparts of the problem.