QCSP made Practical by virtue of Restricted Quantification

Marco Benedetti, Arnaud Lallouet, Jérémie Vautard

The QCSP+ language we introduce extends the framework of Quantified Constraint Satisfaction Problems (QCSPs) by enabling us to neatly express restricted quantifications via a chain of nested CSPs to be interpreted as alternately conjuncted and disjuncted. Restricted quantifiers turn out to be a convenient solution to the crippling modeling issues we encounter in QCSP and — surprisingly — they help to reuse propagation technology and to prune the search space. Our QCSP+ solver — which also handles arithmetic and global constraints — exhibits state-of-the-art performances.

Subjects: 15.2 Constraint Satisfaction


Submitted: Oct 16, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.