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

Language | English |
---|---|

Title of host publication | Integration of AI and OR Techniques in Constraint Programming |

Subtitle of host publication | 14th International Conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017, Proceedings |

Editors | Domenico Salvagnin, Michele Lombardi |

Place of Publication | Cham, Switzerland |

Publisher | Springer |

Pages | 277-292 |

Number of pages | 16 |

ISBN (Electronic) | 9783319597768 |

ISBN (Print) | 9783319597751 |

DOIs | |

State | Published - 2017 |

Event | Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming - Padova, Italy Duration: 5 Jun 2017 → 8 Jun 2017 |

### Publication series

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

Publisher | Springer |

Volume | 10335 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming |
---|---|

Country | Italy |

City | Padova |

Period | 5/06/17 → 8/06/17 |

### Cite this

*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

}

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

Research output: Research - peer-review › Conference Paper

TY - CHAP

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

ER -