Cost-Based Domain Filtering for Stochastic Constraint Programming

R. Rossi, S.A. Tarim, B. Hnich, S. Prestwich

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

7 Citations (Scopus)

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 [9]. 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
Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
EditorsP.J. Stuckey
Pages235-250
DOIs
Publication statusPublished - 2008

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin/Heidelberg
Number5202

Fingerprint Dive into the research topics of 'Cost-Based Domain Filtering for Stochastic Constraint Programming'. Together they form a unique fingerprint.

Cite this