so that given random values for Vs1, we can find values for Vd2, so that given random values for Vs2, the hard constraints are always satisfied and the chance constraints are again satisfied in at least the given fraction of worlds. Note that the values chosen for the second set of decision variables Vd2 are conditioned on both the values chosen for the first set of decision variables Vd1 and on the random values given to the first set of stochastic variables Vs1. This can model situations in which items are produced and can be consumed or put in stock for later consumption. Future production then depends both on previous production (earlier decision variables) and on previous demand (earlier stochastic variables).

An m stage stochastic CSP is defined in an analogous way to one and two stage stochastic CSPs. Note that
[Walsh, 2002] insisted that the stochastic variables take values independently of each other. This prevents us representing a number of common situations. For example, if the market goes down in the first quarter, it is probably more likely to go down in the second quarter. A second stage stochastic variable representing the market index is therefore dependent on the first stage stochastic variable representing the market index. There is, however, nothing in the semantics given for stochastic constraint programs nor in the solution methods proposed in [Walsh, 2002] that used this assumption. We therefore allow later stage stochastic variables to take values which are conditioned by the earlier stage stochastic variables.

A stochastic constraint optimization problem (stochastic COP) is a stochastic CSP plus a cost function defined over the decision and stochastic variables. In [Walsh, 2002], the only goal considered was to find a solution that satisfies the stochastic CSP which minimizes or maximizes the expected value of the objective function. We now extend this to a much wider range of goals. For example, we might wish to limit the downside (i.e. maximize the least value of the cost function),
or to minimize the spread (i.e. minimize the difference between the least and the largest value of the cost function).

## 3 Scenario-Based Semantics

In [Walsh, 2002], a semantics for stochastic constraint programs is given based on policies. A policy is a tree of decisions. Each path in a policy represents a different possible scenario (set of values for the stochastic variables), and the values assigned to decision variables in this scenario. To find satisfying policies, [Walsh, 2002] presents backtracking and forward checking algorithms which explores the implicit AND/OR graph. Stochastic variables give AND nodes as we must find a policy that satisfies all their values, whilst decision variables give OR nodes as we only need find one satisfying value.

An alternative semantics, which suggests an alternative solution method, comes from a scenario-based view
[Birge and Louveaux, 1997]. A scenario is any possible set of values for the stochastic variables. Thus, a scenario is associated with each path in the policy. Within each scenario, we have a conventional (non-stochastic) constraint program to solve. We simply replace the stochastic variables by the values taken in the scenario, and ensure that the values found for the decision variables are consistent across scenarios. Note that certain decision variables are shared acrossscenarios. The first stage decisions are, for example, shared by all scenarios. The great advantage of this approach is that we can use conventional constraint solvers to solve stochastic constraint programs. We do not need to implement specialized solvers. Of course, there is a price to pay as the number of scenarios grows exponentially with the number of stages.

However, our results show that a scenario-based approach is feasible for many problems. Indeed, we observe much better performance using this approach on the production planning example introduced in [Walsh, 2002]. In addition, as we discuss later, we have developed a number of techniques like Latin hypercube sampling to reduce the number of scenarios considered.

## 4 Stochastic Opl

We have implemented this framework on top of the OPL
constraint modelling language [Hentenryck *et al.*, 1999]. An OPL model consists of two parts: a set of declarations, followed by an instruction. Declarations define the data types, (input) data and the (decision) variables. An OPL instruction is either to satisfy a set of constraints or to maximize/minimize an objective function subject to a set of constraints. We have extended the declarations to include the declaration of stochastic variables, and the instructions to include chance constraints, and a range of new goals like maximizing the expectation of an objective function.

## 4.1 Variable Declaration

We now declare both decision and stochastic variables.

Stochastic variables are set according to a probability distribution using a command of the form:

## Stoch <Type> <Id> <Dist>;

Where **<Type>** is (as with decision variables) a data type
(e.g. a range of values, or an enumerated list of values),
<Id> is (as with decision variables) the variable name, and
<Dist> defines the probability distribution of the stochastic variable(s). Probability distributions include **uniform**,
poisson(lambda), and user defined via a list of (not necessarily normalized) values. Other types of distribution can be supported as needed. We insist that stochastic variables are arrays, with the last index describing the stage. Here are some examples:
stoch 0..1 market[Years] uniform; stoch 100..102 demand[Quarter] {1,2,3};
In the first, we have a 0/1 variable in each year which takes either value with equal probability. In the last, we have a demand variable for each quarter, which takes the value 100 in 1 out of 6 cases, 101 in 2 out 6 cases, and 102 in the remaining 3 cases.

## 4.2 Constraint Posting

We can post both hard constraints (as in OPL) and chance constraints. Chance constraints hold in some but not necessarily all scenarios. They are posted using a command of the form: