Stochastic Constraint Programming

Toby Walsh

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.