Stochastic Constraint Programming: A Scenario-Based Approach |
| |
Authors: | S Armagan Tarim Suresh Manandhar Toby Walsh |
| |
Affiliation: | (1) Cork Constraint Computation Centre, Department of Computer Science, University College Cork, Cork, Ireland;(2) Artificial Intelligence Group, Department of Computer Science, University of York, York, UK;(3) National ICT Australia and School of Computer Science and Engineering, University of New South Wales, Sydney, Australia |
| |
Abstract: | To model combinatorial decision problems involving uncertainty and probability, we introduce scenario based stochastic constraint
programming. Stochastic constraint programs contain both decision variables, which we can set, and stochastic variables, which
follow a discrete probability distribution. We provide a semantics for stochastic constraint programs based on scenario trees.
Using this semantics, we can compile stochastic constraint programs down into conventional (non-stochastic) constraint programs.
This allows us to exploit the full power of existing constraint solvers. We have implemented this framework for decision making
under uncertainty in stochastic OPL, a language which is based on the OPL constraint modelling language Van Hentenryck et
al., 1999]. To illustrate the potential of this framework, we model a wide range of problems in areas as diverse as portfolio
diversification, agricultural planning and production/inventory management. |
| |
Keywords: | Constraint programming Constraint satisfaction Reasoning under uncertainty |
本文献已被 SpringerLink 等数据库收录! |
|