Evolving parameterised policies for stochastic constraint programming


Prestwich S., TARIM Ş. A., Rossi R., Hnich B.

15th International Conference on Principles and Practice of Constraint Programming, CP 2009, Lisbon, Portugal, 20 - 24 September 2009, vol.5732 LNCS, pp.684-691 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 5732 LNCS
  • Doi Number: 10.1007/978-3-642-04244-7_53
  • City: Lisbon
  • Country: Portugal
  • Page Numbers: pp.684-691
  • Hacettepe University Affiliated: Yes

Abstract

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. © 2009 Springer Berlin Heidelberg.