Cost-Based Domain Filtering for Stochastic Constraint Programming
14th International Conference on Principles and Practice of Constraint Programming (CP 2008), Sydney, Australia, 14 - 18 September 2008, vol.5202, pp.235-237, (Full Text)
- 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
- Open Archive Collection: AVESIS Open Access Collection
- Hacettepe University Affiliated: Yes
Abstract
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.