TY - GEN
T1 - Evolving parameterised policies for stochastic constraint programming
AU - Prestwich, Steven
AU - Tarim, S. Armagan
AU - Rossi, Roberto
AU - Hnich, Brahim
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/70350423545
U2 - 10.1007/978-3-642-04244-7_53
DO - 10.1007/978-3-642-04244-7_53
M3 - Conference proceeding
AN - SCOPUS:70350423545
SN - 3642042430
SN - 9783642042430
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 684
EP - 691
BT - Principles and Practice of Constraint Programming - CP 2009 - 15th International Conference, CP 2009, Proceedings
T2 - 15th International Conference on Principles and Practice of Constraint Programming, CP 2009
Y2 - 20 September 2009 through 24 September 2009
ER -