Scenario-based learning for stochastic combinatorial optimisation

David Hemmi, Guido Tack, Mark Wallace

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

    2 Citations (Scopus)

    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.

    Original 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
    EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2017 - Padova, Italy
    Duration: 5 Jun 20178 Jun 2017
    Conference number: 14th
    https://cpaior2017.dei.unipd.it/ (Conference website)
    https://link.springer.com/book/10.1007/978-3-319-59776-8 (Proceedings)

    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

    ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2017
    Abbreviated titleCPAIOR 2017
    CountryItaly
    CityPadova
    Period5/06/178/06/17
    Internet address

    Cite this