Cost-Based Domain Filtering for Stochastic Constraint Programming

Creative Commons License

Rossi R., TARIM Ş. A., HNİCH B., Prestwich S.

14th International Conference on Principles and Practice of Constraint Programming (CP 2008), Sydney, Australia, 14 - 18 September 2008, vol.5202, pp.235-237 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 5202
  • Doi Number: 10.1007/978-3-540-85958-1_16
  • City: Sydney
  • Country: Australia
  • Page Numbers: pp.235-237
  • Hacettepe University Affiliated: Yes


Cost based filtering is a novel approach that combines techniques from Operations Research and Constraint Programming to filter from decision variable domains values that, do not lead to better solutions [7]. Stochastic: Constraint Programming is a. framework for modeling combinatorial optimization problems that, involve uncertainty [19]. In this work; we show how to perform cost; based filtering for certain classes of stochastic constraint, programs. Our approach is based oil a set of known inequalities borrowed from Stochastic Programming - a branch of OR. concerned with modeling and solving problems involving. uncertainty. We discuss bound generation and cost-based domain filtering procedures for a well-known problem in the Stochastic. Programming literature, the static stochastic knapsack problem. We also apply our technique to a stochastic sequencing problem. Our results clearly show the value of the proposed approach over;I pure scenario-based Stochastic Constraint Programming formulation both in terms of explored nodes and run times.