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

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 publicationProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 )
Subtitle of host publicationNew Orleans, Louisiana USA — February 2–7, 2018
EditorsSheila McIlraith, Kilian Weinberger
Place of PublicationPalo Alto CAL 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
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
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.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 ): New Orleans, Louisiana USA — February 2–7, 2018 (pp. 1322-1329). Palo Alto CAL USA: Association for the Advancement of Artificial Intelligence (AAAI).
Hemmi, David ; Tack, Guido ; Wallace, Mark. / A recursive scenario decomposition algorithm for combinatorial multistage stochastic optimisation problems. Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 ): New Orleans, Louisiana USA — February 2–7, 2018. editor / Sheila McIlraith ; Kilian Weinberger. Palo Alto CAL USA : Association for the Advancement of Artificial Intelligence (AAAI), 2018. pp. 1322-1329
@inproceedings{37105c522174496698862bd518e90d7f,
title = "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.",
author = "David Hemmi and Guido Tack and Mark Wallace",
year = "2018",
language = "English",
pages = "1322--1329",
editor = "McIlraith, {Sheila } and Weinberger, {Kilian }",
booktitle = "Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 )",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
address = "United States",

}

Hemmi, D, Tack, G & Wallace, M 2018, A recursive scenario decomposition algorithm for combinatorial multistage stochastic optimisation problems. in S McIlraith & K Weinberger (eds), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 ): New Orleans, Louisiana USA — February 2–7, 2018. Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CAL USA, pp. 1322-1329, AAAI Conference on Artificial Intelligence 2018, New Orleans, United States, 2/02/18.

A recursive scenario decomposition algorithm for combinatorial multistage stochastic optimisation problems. / Hemmi, David; Tack, Guido; Wallace, Mark.

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 ): New Orleans, Louisiana USA — February 2–7, 2018. ed. / Sheila McIlraith; Kilian Weinberger. Palo Alto CAL USA : Association for the Advancement of Artificial Intelligence (AAAI), 2018. p. 1322-1329.

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

TY - GEN

T1 - A recursive scenario decomposition algorithm for combinatorial multistage stochastic optimisation problems

AU - Hemmi, David

AU - Tack, Guido

AU - Wallace, Mark

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85060479315&partnerID=8YFLogxK

M3 - Conference Paper

SP - 1322

EP - 1329

BT - Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 )

A2 - McIlraith, Sheila

A2 - Weinberger, Kilian

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto CAL USA

ER -

Hemmi D, Tack G, Wallace M. A recursive scenario decomposition algorithm for combinatorial multistage stochastic optimisation problems. In McIlraith S, Weinberger K, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18 ): New Orleans, Louisiana USA — February 2–7, 2018. Palo Alto CAL USA: Association for the Advancement of Artificial Intelligence (AAAI). 2018. p. 1322-1329