Combinatorial optimisation problems often contain uncertainty that has to be taken into account to produce realistic solutions. A common way to describe the uncertainty is by means of scenarios, where each scenario describes 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 subject to uncertainty. The goal of my PhD is to develop generic methods for solving stochastic combinatorial optimisation problems formulated in a Constraint Programming framework.

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.

Combinatorial optimisation problems often contain uncertainty that has to be taken into account to pro- duce realistic solutions. One way of describing the uncertainty is using scenarios, where each sce- nario describes different potential sets of problem parameters based on random distributions or his- torical data. While efficient algorithmic techniques exist for specific problem classes such as linear pro- grams, there are very few approaches that can han- dle general Constraint Programming formulations with uncertainty. The goal of my PhD is to develop generic methods for solving stochastic combina- torial optimisation problems formulated in a Con- straint Programming framework.