Synthesizing Filtering Algorithms for Global Chance-Constraints

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

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract / Description of output

Stochastic Constraint Satisfaction Problems (SCSPs) are a powerful modeling framework for problems under uncertainty. To solve them is a P-Space task. The only solution approach to date compiles down SCSPs into classical CSPs. This allows the reuse of classical constraint solvers to solve SCSPs, but at the cost of increased space requirements and weak constraint propagation. This paper tries to overcome some of these drawbacks by automatically synthesizing filtering algorithms for global chance-constraints. These filtering algorithms are parameterized by propagators for the deterministic version of the chance-constraints. This approach allows the reuse of existing propagators in current constraint solvers and it enhances constraint propagation. Experiments show the benefits of this novel approach.
Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - CP 2009
Subtitle of host publication15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009 Proceedings
EditorsIan P. Gent
PublisherSpringer-Verlag GmbH
Pages439-453
Number of pages15
Volume5732 LNCS
ISBN (Print)978-3-642-04243-0
DOIs
Publication statusPublished - 19 Sept 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Berlin / Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'Synthesizing Filtering Algorithms for Global Chance-Constraints'. Together they form a unique fingerprint.

Cite this