Stochastic Constraint Programming is an extension of Constraint Programming for modelling and solving combinatorial problems involving uncertainty. A solution to such a problem is a policy tree that specifies decision variable assignments in each scenario. Several solution methods have been proposed but none seems practical for large multi-stage problems. We propose an incomplete approach: specifying a policy tree indirectly by a parameterised function, whose parameter values are found by evolutionary search. On some problems this method is orders of magnitude faster than a state-of-the-art scenario-based approach, and it also provides a very compact representation of policy trees.
|Title of host publication||Principles and Practice of Constraint Programming - CP 2009|
|Subtitle of host publication||15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009 Proceedings|
|Editors||Ian P. Gent|
|Number of pages||8|
|Publication status||Published - 19 Sept 2009|
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Publisher||Springer Berlin / Heidelberg|