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 . Stochastic Constraint Programming is a framework for modeling combinatorial optimization problems that involve uncertainty . In this work, we show how to perform cost-based filtering for certain classes of stochastic constraint programs. Our approach is based on 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 a pure scenario-based Stochastic Constraint Programming formulation both in terms of explored nodes and run times.
|Title of host publication||Principles and Practice of Constraint Programming|
|Subtitle of host publication||14th International Conference, CP 2008, Sydney, Australia, September 14-18, 2008. Proceedings|
|Editors||Peter J. Stuckey|
|Number of pages||16|
|Publication status||Published - 22 Sep 2008|
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Publisher||Springer Berlin / Heidelberg|