
| Backtracking (BT)   | Forward Checking (FC)   | Scenario-Based (SB)   |           |         |         |               |         |
|---------------------|-------------------------|-----------------------|-----------|---------|---------|---------------|---------|
| No. Stages          | Nodes                   | CPU/sec               | Nodes     | CPU/sec | Failure | Choice Points | CPU/sec |
| 1                   | 28                      | 0.01                  | 10        | 0.01    | 4       | 5             | 0.00    |
| 2                   | 650                     | 0.09                  | 148       | 0.03    | 4       | 8             | 0.02    |
| 3                   | 17,190                  | 2.72                  | 3,604     | 0.76    | 8       | 24            | 0.16    |
| 4                   | 510,356                 | 83.81                 | 95,570    | 19.07   | 42      | 125           | 1.53    |
| 5                   | 15,994,856              | 3,245.99              | 2,616,858 | 509.95  | 218     | 690           | 18.52   |
| 6                   | -                       | -                     | -         | -       | 1260    | 4035          | 474.47  |

## Theorem 1. Stochastic Constraint Satisfaction Problems Are Pspace-Complete.

Proof: **Membership in PSPACE follows from the existence of a naive depth-first and/or search tree**
algorithm for solving stochastic constraint satisfaction **problems. This algorithm recurses through the**
variables in order, making an "and" branch for a stochastic variable and an "or" branch for a decision variable. The algorithm requires linear space in the number **of variables.**
To show completeness, we reduce the satisfiability of quantified Boolean formula to a stochastic constraint satisfaction problem. Each existential Boolean variable in the quantified Boolean formula is mapped to a Boolean decision variable in the stochastic CSP. Each universal Boolean variable in the quantified Boolean formula is mapped to a Boolean stochastic **variable in the stochastic CSP. Such**
variables have equal probability of being true or f alse**. Each clause is replaced by the equivalent**
constraint which is to be satisfied in all possible scenarios. The reduction is linear in the size of the original quantified Boolean formula. The quantified Boolean **formula is satisfiable iff the stochastic** CSP is itself satisfiable. ⋄

## 4 Stochastic Opl

We have implemented this framework on top of the OPL constraint modelling language [10]. An OPL
model consists of two parts: a set of declarations, followed **by an instruction. Declarations define the** data types, constants and 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 Constant And Variable Declarations

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