Blocksolve: A bottom-up approach for solving quantified CSPs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

Blocksolve: A bottom-up approach for solving quantified CSPs

Résumé

Thanks to its extended expressiveness, the quantified constraint satisfaction problem (QCSP) can be used to model problems that are difficult to express in the standard CSP formalism. This is only recently that the constraint community got interested in QCSP and proposed algorithms to solve it. In this paper we propose BlockSolve, an algorithm for solving QCSPs that factorizes computations made in branches of the search tree. Instead of following the order of the variables in the quantification sequence, our technique searches for combinations of values for existential variables at the bottom of the tree that will work for (several) values of universal variables earlier in the sequence. An experimental study shows the good performance of BlockSolve compared to a state of the art QCSP solver.
Fichier principal
Vignette du fichier
cp06-qcsp.pdf (222.5 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-00135534 , version 1 (08-03-2007)

Identifiants

Citer

Guillaume Verger, Christian Bessiere. Blocksolve: A bottom-up approach for solving quantified CSPs. CP: Principles and Practice of Constraint Programming, Sep 2006, Nantes, France. pp.635-649, ⟨10.1007/11889205_45⟩. ⟨lirmm-00135534⟩
101 Consultations
196 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More