Cost-Based Domain Filtering for Stochastic Constraint Programming

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.