In this paper, we extend this framework to make it more useful **practically. In particular, we permit**
multiple chance constraints and a range of different objectives. As each such extension requires large changes to the backtracking and forward checking algorithms, we propose instead a scenario based view of stochastic constraint programs. One of the major advantages of this approach is that stochastic constraint programs can then be compiled down into conventional (non-stochastic) constraint programs. This compilation allows us to use existing constraint solvers without any modification, as well as call upon the power of hybrid solvers which combine constraint solving and integer programming techniques. We also propose a number of techniques to reduce the number of scenarios and to generate robust solutions. This framework combines together some of the best features of traditional constraint satisfaction, stochastic integer programming **[24], and stochastic satisfiability [14]. 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]. Finally, we describe a wide range of problems that we have modelled in Stochastic OPL that illustrate some of its potential.

## 2 Motivation Example

We consider a stochastic version of the "template design" problem. The *deterministic* **template design**
problem (prob002 in CSPLib, http://www.csplib.org) is described as follows. We are given a set of variations of a design, with a common shape and size and such that the number of required "pressings" of each variation is known. The problem is to design a set of templates, with a common capacity to which each must be filled, by assigning one or more instances of a variation to each template. A design should be chosen that minimises the total number of "runs" of **the templates required to satisfy the**
number of pressings required for each variation. As an example, the variations might be for cartons for different flavours of cat food, such as fish or chicken, where **ten thousand fish cartons and twenty** thousand chicken cartons need to be printed. The problem would then be to design a set of templates by assigning a number of fish and/or chicken designs to each template such that a minimal number of runs of the templates is required to print all thirty thousand cartons. Proll and Smith address this problem by fixing the number of templates and minimising the total number of pressings [20].

In the *stochastic* **version of the problem, the demand for each variation is uncertain. We adopt the**
Proll–Smith model in what follows, extending it to comply with the stochastic demand assumption. We use the following notation for problem parameters: N, number of variations; T**, number of templates;**
S, number of slots on each template; ch, unit scrap cost for excess inventory; cp**, unit shortage cost.** The decision variables are: ai,j , number of slots designated to variation i, on template j; Rj **, number**
of required "runs" of template j. For convenience, we define the following auxiliary variables: xi**, total** production for variation i; ei, total scrap in variation i; bi, total shortage in variation i**. There are also**
stochastic variables di **representing stochastic demand for variation** i.

This problem can be modelled as stochastic constraint optimization problem. There is a constraint to ensure that the total number of slots designated to variations is exactly the number of slots available, which is S. 

X
N
$$\{a_{i j}=S,\quad\forall j\in\{1,...,T\},$$
i=1
aij = S, ∀j ∈ {1, ..., T}, (1)
2