Hybrid Metaheuristics for Stochastic Constraint Programming

Abstract

Stochastic Constraint Programming (SCP) is an extension of Constraint Programming for modelling and solving combinatorial problems involving uncertainty. This paper proposes a metaheuristic approach to SCP that can scale up to large problems better than state-of-the-art complete methods, and exploits standard filtering algorithms to handle hard constraints more efficiently. For problems with many scenarios it can be combined with scenario reduction and sampling methods.