Filtering Algorithms for Global Chance Constraints

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

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (Scopus)

Abstract

Stochastic Constraint Satisfaction Problems (SCSPs) are a powerful modeling framework for problems under uncertainty. To solve them is a PSPACE task. The only complete solution approach to date — scenario-based stochastic constraint programming — compiles SCSPs down 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 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 has the potential to enhance constraint propagation. Our results show that, for the test bed considered in this work, our approach is superior to scenario-based stochastic constraint programming. For these instances, our approach is more scalable, it produces more compact formulations, it is more efficient in terms of run time and more effective in terms of pruning for both stochastic constraint satisfaction and optimization problems.
Original languageEnglish
Pages (from-to)69-94
JournalArtificial Intelligence
Volume189
DOIs
Publication statusPublished - 2012

Keywords

  • Filtering algorithms
  • Global chance constraints
  • Stochastic alldifferent
  • Stochastic constraint programming
  • Stochastic constraint satisfaction

Fingerprint

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

Cite this