Evolving parameterised policies for stochastic constraint programming

S. Prestwich, S.A. Tarim, R. Rossi, B. Hnich

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - CP 2009
Subtitle of host publication15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009 Proceedings
EditorsIan P. Gent
PublisherSpringer-Verlag GmbH
Number of pages8
Volume5732 LNCS
Publication statusPublished - 19 Sept 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Berlin / Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Evolving parameterised policies for stochastic constraint programming'. Together they form a unique fingerprint.

Cite this