search in production/inventory management. As the expected cost of the robust solution is always higher, the tradeoff between nervousness and cost may have to be taken into account.

## 10 Related And Future Work

Stochastic constraint programs are closely related to Markov decision problems (MDPs) [Puterman, 1994]. Stochastic constraint programs can, however, model problems which lack the Markov property that the next state and reward depend only on the previous state and action taken. The current decision in a stochastic constraint program will often depend on all earlier decisions. To model this as an MDP, we would need an exponential number of states. Another significant difference is that stochastic constraint programs by using a scenario-based interpretation can immediately call upon complex and powerful constraint propagation techniques.

Stochastic constraint programming was inspired by both stochastic integer programming and stochastic satisfiability
[Littman *et al.*, 2000]. It is designed to take advantage of some of the best features of each framework. For example, we are able to write expressive models using non-linear and global constraints, and to exploit efficient constraint propagation algorithms. In operations research, scenarios are used in stochastic programming. Indeed, the scenario reduction techniques of Dupacova, Growe-Kuska and Romisch
[Dupacova *et al.*, 2002] implemented here are borrowed directly from stochastic programming.

There are a number of extensions of conventional constraint satisfaction problem to model constraints that are uncertain, probabilistic or not necessarily satisfied. For example, in probabilistic constraint satisfaction each constraint has a certain probability independent of all other probabilities of being part of the problem [Fargier and Lang, 1993] whilst in semi-ring constraint satisfaction each tuple in a constraint has a value associated with it [Bistarelli *et al.*, 1996]. However, none of these extensions deal with variables that may have uncertain or probabilistic values. Stochastic constraint programming could, however, easily be combined with most of these techniques.

## 11 Conclusions

To model combinatorial decision problems involving uncertainty and probability, we have extended the stochastic constraint programming framework proposed in [Walsh, 2002]
along a number of important dimensions. In particular, we have relaxed the assumption that stochastic variables are independent, and added multiple chance constraints as well as a range of objective functions like maximizing the downside. We have also provided a new (but equivalent) semantics for stochastic constraint programs based on scenarios.

Based on this semantics, we can compile stochastic constraint programs down into conventional (non-stochastic) constraint programs. The advantage of this compilation is that we can use the full power of existing constraint solvers without any modification. We have also proposed 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
[Hentenryck *et al.*, 1999]. 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, we want to explore more sophisticated notions of solution robustness
(e.g. limiting the range of values used by a decision variable).

## Acknowledgements

This project was funded by EPSRC under GR/R30792, and the Science Foundation Ireland. We thank the members of the APES Research Group and 4C Lab for their feedback.

References
[Birge and Louveaux, 1997] J. R. Birge and F. Louveaux. *Introduction to Stochastic Programming*. Springer-Verlag, New York, 1997.

[Bistarelli *et al.*, 1996] S. Bistarelli, H. Fargier, U. Montanari, F. Rossi, T. Schiex, and G. Verfaillie. Semi-ring based CSPs and valued CSPs: Basic properties and comparison. In M. Jample, E. Freuder, and M. Maher, editors, *Over-Constrained Systems*, pages 111–150. SpringerVerlag, 1996. LNCS 1106.

[Dupacova *et al.*, 2002] J. Dupacova, N. Growe-Kuska, and W. Romisch. Scenario reduction in stochastic programming: an approach using probability metrics. *Mathematical Programming*, To appear, 2002.

[Fargier and Lang, 1993] H. Fargier and J. Lang. Uncertainty in constraint satisfaction problems: a probabilistic approac h. In *Proceedings of ECSQARU*. Springer-Verlag, 1993. LNCS 747.

[Hentenryck *et al.*, 1999] P. Van Hentenryck, L. Michel, L. Perron, and J-C. Regin. Constraint programming in OPL. In G. Nadathur, editor, Principles and Practice of Declarative Programming, pages 97–116. SpringerVerlag, 1999. Lecture Notes in Computer Science 1702.

[Kouvelis and Yu, 1996] P. Kouvelis and G. Yu. *Robust Discrete Optimization and Its Applications*. Nonconvex optimization and its applications: volume 14. Kluwer, 1996.

[Littman *et al.*, 2000] M.L. Littman, S.M. Majercik, and T. Pitassi. Stochastic Boolean satisfiability. Journal of Automated Reasoning, 2000.

[McKay *et al.*, 1979] M.D. McKay, R.J. Beckman, and W.J.

Conover. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. *Technometrics*, 21(2):239–245, 1979.

[Puterman, 1994] M.L. Puterman. *Markov decision processes: discrete stochastic dynamic programming*. John Wiley and Sons, 1994.

[Walsh, 2002] Toby Walsh. Stochastic constraint programming. In *Proceedings of the 15th ECAI*. European Conference on Artificial Intelligence, IOS Press, 2002.