TY - GEN
T1 - Synthesizing Filtering Algorithms for Global Chance-Constraints
AU - Hnich, Brahim
AU - Rossi, Roberto
AU - Tarim, S. Armagan
AU - Prestwich, Steven
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/70350413804
U2 - 10.1007/978-3-642-04244-7_36
DO - 10.1007/978-3-642-04244-7_36
M3 - Conference contribution
AN - SCOPUS:70350413804
SN - 3642042430
SN - 9783642042430
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 439
EP - 453
BT - Principles and Practice of Constraint Programming - CP 2009 - 15th International Conference, CP 2009, Proceedings
T2 - 15th International Conference on Principles and Practice of Constraint Programming, CP 2009
Y2 - 20 September 2009 through 24 September 2009
ER -