constraint optimization problem.

Branching constraint satisfaction [8] models problems in which there is uncertainty in the number of variables. For example, we can model a nurse rostering problem by assigning shifts to nurses. Branching constraint satisfaction then allows us to deal with the uncertainty in which nurses are available for duty. We can represent such problems with a stochastic CSP with a stochastic 0/1 variable for each nurse representing their availability.

A number of extensions of the traditional constraint satisfaction problem model constraints that are uncertain, probabilistic or not necessarily satisfied (see, for instance, [5, 3, 28]). In partial constraint satisfaction we maximize the number of constraints satisfied [9]. As a second example, in probabilistic constraint satisfaction each constraint has a certain probability independent of all other probabilities of being part of the problem [5]. As a third example, both valued and semi-ring based constraint satisfaction [3] generalizes probabilistic constraint satisfaction as well as a number of other frameworks. In semi-ring based constraint satisfaction, a value is associated with each tuple in a constraint, whilst in valued constraint satisfaction, a value is associated with each constraint. As a fourth example, the certainty closure model [28] permits constraints to have parameters whose values are uncertain. This differs from stochastic constraint programming in three significant ways. First, stochastic variables come with probability distributions in our framework, whilst the uncertain parameters in the certainty closure model take any of their possible values. Second, we find a policy which may react differently according to the values taken by the stochastic variables, whilst the certainty closure model aims to find the decision space within which all possible solutions must be contained. Third, stochastic constraint programs can have multiple stages whilst certainty closure models are essentially one stage.

Stochastic constraint programming can easily be combined with most of these techniques. For example, we can define stochastic partial constraint satisfaction in **which we maximize the number of satisfied**
constraints, or stochastic probabilistic constraint satisfaction in which each constraint has an associated probability of being in the problem.

## 12 Conclusions 23

We have described stochastic constraint programming, an extension of constraint programming to deal with both decision variables (which we can set) and stochastic variables (which follow some probability distribution). This framework is designed to take advantage of the best features of traditional constraint satisfaction, stochastic integer programming, and stochastic satisfiability. It can be used to model a wide variety of decision problems involving uncertainty and probability. We have provided a semantics for stochastic constraint programs based on scenarios. We have shown how to compile stochastic constraint programs down into conventional (non-stochastic) constraint programs. We can therefore call upon the full power of existing constraint solvers without any modification. We have also described a number of techniques to reduce the number of scenarios, and to generate robust solutions.

We have implemented this framework for decision making under uncertainty in a language called stochastic OPL. This is an extension of the OPL constraint modelling language [10]. To illustrate the potential of this framework, we have modelled a wide range of **problems in areas as diverse as finance,**
agriculture and production. There are many directions for future work. For example, we want to allow the user to define a limited set of scenarios that are representative of the whole. As a second example,