A Recursive Scenario Decomposition Algorithm for Combinatorial Multistage Stochastic Optimisation Problems
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.
Cite
Text
Hemmi et al. "A Recursive Scenario Decomposition Algorithm for Combinatorial Multistage Stochastic Optimisation Problems." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11525Markdown
[Hemmi et al. "A Recursive Scenario Decomposition Algorithm for Combinatorial Multistage Stochastic Optimisation Problems." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/hemmi2018aaai-recursive/) doi:10.1609/AAAI.V32I1.11525BibTeX
@inproceedings{hemmi2018aaai-recursive,
title = {{A Recursive Scenario Decomposition Algorithm for Combinatorial Multistage Stochastic Optimisation Problems}},
author = {Hemmi, David and Tack, Guido and Wallace, Mark},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2018},
pages = {1322-1329},
doi = {10.1609/AAAI.V32I1.11525},
url = {https://mlanthology.org/aaai/2018/hemmi2018aaai-recursive/}
}