Stochastic Constraint Programming

Contents

To model decision problems involving uncertainty and probability, we propose stochastic constraint programming. Stochastic constraint programs contain both decision variables (which we can set) and stochastic variables (which follow some probability distribution), and combine together the best features of traditional constraint satisfaction, stochastic integer programming, and stochastic satisfiability. We give a semantics for stochastic constraint programs, and propose a number of complete algorithms and approximation procedures. Using these algorithms, we observe phase transition behavior in stochastic constraint programs. Interestingly, the cost of both optimization and satisfaction peaks in the satisfaction phase boundary. Finally, we discuss a number of extensions of stochastic constraint programming to relax various assumptions like the independence between stochastic variables.