Stochastic Constraint Programming: A Scenario-Based Approach

To model combinatorial decision problems involving uncertainty and probability, the authors introduce scenario based stochastic constraint programming. Stochastic constraint programs contain both decision variables, which they can set, and stochastic variables, which follow a discrete probability distribution. They provide a semantics for stochastic constraint programs based on scenario trees. Using this semantics, they can compile stochastic constraint programs down into conventional (nonstochastic) constraint programs. This allows one to exploit the full power of existing constraint solvers.