Hybrid Metaheuristics for Stochastic Constraint Programming

Stochastic Constraint Programming (SCP) is an extension of Constraint Programming for modelling and solving combinatorial problems involving uncertainty. This paper makes three contributions to the field. Firstly we propose a metaheuristic approach to SCP that scales up to large problems better than stateof-the-art complete methods. Secondly we show how to use standard filtering algorithms to handle hard constraints more efficiently during search. Thirdly we extend our approach to problems with endogenous uncertainty, in which probability distributions are affected by decisions. This extension enables SCP to model and solve a wider class of problems.