A recursive scenario decomposition algorithm for combinatorial multistage stochastic optimisation problems

David Hemmi, Guido Tack, Mark Wallace

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationThe Thirty-Second AAAI Conference on Artificial Intelligence
EditorsSheila McIlraith, Kilian Weinberger
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages1322-1329
Number of pages8
ISBN (Electronic)9781577358008
Publication statusPublished - 2018
EventAAAI Conference on Artificial Intelligence 2018 - New Orleans, United States of America
Duration: 2 Feb 20187 Feb 2018
Conference number: 32nd
https://aaai.org/Conferences/AAAI-18/

Conference

ConferenceAAAI Conference on Artificial Intelligence 2018
Abbreviated titleAAAI 2018
CountryUnited States of America
CityNew Orleans
Period2/02/187/02/18
Internet address

Cite this

Hemmi, D., Tack, G., & Wallace, M. (2018). A recursive scenario decomposition algorithm for combinatorial multistage stochastic optimisation problems. In S. McIlraith, & K. Weinberger (Eds.), The Thirty-Second AAAI Conference on Artificial Intelligence (pp. 1322-1329). Association for the Advancement of Artificial Intelligence (AAAI). https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/viewPDFInterstitial/16699/15825