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, Avustralya, 14 - 18 Eylül 2008, cilt.5202, ss.235-237 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 5202
  • Doi Numarası: 10.1007/978-3-540-85958-1_16
  • Basıldığı Şehir: Sydney
  • Basıldığı Ülke: Avustralya
  • Sayfa Sayıları: ss.235-237
  • Hacettepe Üniversitesi Adresli: Evet

Özet

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.