Scenario-based learning for stochastic combinatorial optimisation

David Hemmi, Guido Tack, Mark Wallace

Research output: Chapter in Book/Report/Conference proceedingConference Paper

Abstract

Combinatorial optimisation problems often contain uncertainty that has to be taken into account to produce realistic solutions. This uncertainty is usually captured in scenarios, which describe different potential sets of problem parameters based on random distributions or historical data. While efficient algorithmic techniques exist for specific problem classes such as linear programs, there are very few approaches that can handle general Constraint Programming formulations with uncertainty. This paper presents a generic method for solving stochastic combinatorial optimisation problems by combining a scenario-based decomposition approach with Lazy Clause Generation and strong scenario-independent nogoods over the first stage variables. The algorithm can be implemented based on existing solving technology, is easy to parallelise, and is shown experimentally to scale well with the number of scenarios.

LanguageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming
Subtitle of host publication14th International Conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017, Proceedings
EditorsDomenico Salvagnin, Michele Lombardi
Place of PublicationCham, Switzerland
PublisherSpringer
Pages277-292
Number of pages16
ISBN (Electronic)9783319597768
ISBN (Print)9783319597751
DOIs
StatePublished - 2017
EventConference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming - Padova, Italy
Duration: 5 Jun 20178 Jun 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume10335
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceConference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming
CountryItaly
CityPadova
Period5/06/178/06/17

Cite this

Hemmi, D., Tack, G., & Wallace, M. (2017). Scenario-based learning for stochastic combinatorial optimisation. In D. Salvagnin, & M. Lombardi (Eds.), Integration of AI and OR Techniques in Constraint Programming : 14th International Conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017, Proceedings (pp. 277-292). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10335 ). Cham, Switzerland: Springer. DOI: 10.1007/978-3-319-59776-8_23
Hemmi, David ; Tack, Guido ; Wallace, Mark. / Scenario-based learning for stochastic combinatorial optimisation. Integration of AI and OR Techniques in Constraint Programming : 14th International Conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017, Proceedings. editor / Domenico Salvagnin ; Michele Lombardi. Cham, Switzerland : Springer, 2017. pp. 277-292 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{79a4202def8146e5a956851042724af2,
title = "Scenario-based learning for stochastic combinatorial optimisation",
abstract = "Combinatorial optimisation problems often contain uncertainty that has to be taken into account to produce realistic solutions. This uncertainty is usually captured in scenarios, which describe different potential sets of problem parameters based on random distributions or historical data. While efficient algorithmic techniques exist for specific problem classes such as linear programs, there are very few approaches that can handle general Constraint Programming formulations with uncertainty. This paper presents a generic method for solving stochastic combinatorial optimisation problems by combining a scenario-based decomposition approach with Lazy Clause Generation and strong scenario-independent nogoods over the first stage variables. The algorithm can be implemented based on existing solving technology, is easy to parallelise, and is shown experimentally to scale well with the number of scenarios.",
author = "David Hemmi and Guido Tack and Mark Wallace",
year = "2017",
doi = "10.1007/978-3-319-59776-8_23",
language = "English",
isbn = "9783319597751",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "277--292",
editor = "Salvagnin, {Domenico } and Lombardi, {Michele }",
booktitle = "Integration of AI and OR Techniques in Constraint Programming",

}

Hemmi, D, Tack, G & Wallace, M 2017, Scenario-based learning for stochastic combinatorial optimisation. in D Salvagnin & M Lombardi (eds), Integration of AI and OR Techniques in Constraint Programming : 14th International Conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10335 , Springer, Cham, Switzerland, pp. 277-292, Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, Padova, Italy, 5/06/17. DOI: 10.1007/978-3-319-59776-8_23

Scenario-based learning for stochastic combinatorial optimisation. / Hemmi, David; Tack, Guido; Wallace, Mark.

Integration of AI and OR Techniques in Constraint Programming : 14th International Conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017, Proceedings. ed. / Domenico Salvagnin; Michele Lombardi. Cham, Switzerland : Springer, 2017. p. 277-292 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10335 ).

Research output: Chapter in Book/Report/Conference proceedingConference Paper

TY - GEN

T1 - Scenario-based learning for stochastic combinatorial optimisation

AU - Hemmi,David

AU - Tack,Guido

AU - Wallace,Mark

PY - 2017

Y1 - 2017

N2 - Combinatorial optimisation problems often contain uncertainty that has to be taken into account to produce realistic solutions. This uncertainty is usually captured in scenarios, which describe different potential sets of problem parameters based on random distributions or historical data. While efficient algorithmic techniques exist for specific problem classes such as linear programs, there are very few approaches that can handle general Constraint Programming formulations with uncertainty. This paper presents a generic method for solving stochastic combinatorial optimisation problems by combining a scenario-based decomposition approach with Lazy Clause Generation and strong scenario-independent nogoods over the first stage variables. The algorithm can be implemented based on existing solving technology, is easy to parallelise, and is shown experimentally to scale well with the number of scenarios.

AB - Combinatorial optimisation problems often contain uncertainty that has to be taken into account to produce realistic solutions. This uncertainty is usually captured in scenarios, which describe different potential sets of problem parameters based on random distributions or historical data. While efficient algorithmic techniques exist for specific problem classes such as linear programs, there are very few approaches that can handle general Constraint Programming formulations with uncertainty. This paper presents a generic method for solving stochastic combinatorial optimisation problems by combining a scenario-based decomposition approach with Lazy Clause Generation and strong scenario-independent nogoods over the first stage variables. The algorithm can be implemented based on existing solving technology, is easy to parallelise, and is shown experimentally to scale well with the number of scenarios.

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

U2 - 10.1007/978-3-319-59776-8_23

DO - 10.1007/978-3-319-59776-8_23

M3 - Conference Paper

SN - 9783319597751

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 277

EP - 292

BT - Integration of AI and OR Techniques in Constraint Programming

PB - Springer

CY - Cham, Switzerland

ER -

Hemmi D, Tack G, Wallace M. Scenario-based learning for stochastic combinatorial optimisation. In Salvagnin D, Lombardi M, editors, Integration of AI and OR Techniques in Constraint Programming : 14th International Conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017, Proceedings. Cham, Switzerland: Springer. 2017. p. 277-292. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Available from, DOI: 10.1007/978-3-319-59776-8_23