A Recursive Scenario Decomposition Algorithm for Combinatorial Multistage Stochastic Optimisation Problems

Authors

  • David Hemmi Monash University; Data61
  • Guido Tack Monash University; Data61
  • Mark Wallace Monash University

Keywords:

Computer Science, Stochastic Programming, Constraint Programming

Abstract

Stochastic programming is concerned with decision making under uncertainty, seeking an optimal policy with respect to a set of possible future scenarios. This paper looks at multistage decision problems where the uncertainty is revealed over time. First, decisions are made with respect to all possible future scenarios. Secondly, after observing the random variables, a set of scenario specific decisions is taken. Our goal is to develop algorithms that can be used as a back-end solver for high-level modeling languages. In this paper we propose a scenario decomposition method to solve multistage stochastic combinatorial decision problems recursively. Our approach is applicable to general problem structures, utilizes standard solving technology and is highly parallelizable. We provide experimental results to show how it efficiently solves benchmarks with hundreds of scenarios.

Downloads

Published

2018-04-25

How to Cite

Hemmi, D., Tack, G., & Wallace, M. (2018). A Recursive Scenario Decomposition Algorithm for Combinatorial Multistage Stochastic Optimisation Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11525

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization