Scenario-based learning for stochastic combinatorial optimisation

David Hemmi, Guido Tack, Mark Wallace

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

    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
    Publication statusPublished - 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. https://doi.org/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. https://doi.org/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 PaperResearchpeer-review

    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

    A2 - Salvagnin, Domenico

    A2 - Lombardi, Michele

    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)). https://doi.org/10.1007/978-3-319-59776-8_23