QCSP-Solve: A Solver for Quantified Constraint Satisfaction Problems
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 138-142.
Abstract
The Quantified Constraint Satisfaction Problem (QCSP) is a generalization of the CSP in which some variables are universally quantified. It has been shown that a solver based on an encoding of QCSP into QBF can outperform the existing direct QCSP approaches by several orders of magnitude. In this paper we introduce an efficient QCSP solver. We show how knowledge learned from the successful encoding of QCSP into QBF can be utilized to enhance the existing QCSP techniques and speed up search by orders of magnitude. We also show how the performance of the solver can be further enhanced by incorporating advanced lookback techniques such as CBJ and solution-directed pruning. Experiments demonstrate that our solver is several orders of magnitude faster than existing direct approaches to QCSP solving, and significantly outperforms approaches based on encoding QCSPs as QBFs.
@inproceedings{ijcai2005p73,
title = {QCSP-Solve: A Solver for Quantified Constraint Satisfaction Problems},
author = {Gent, Ian P. and Nightingale, Peter and Stergiou, Kostas},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {138--142},
year = {2005},
url = {https://ijcai.org/proceedings/2005/73},
}
TY - CPAPER TI - QCSP-Solve: A Solver for Quantified Constraint Satisfaction Problems AU - Gent, Ian P. AU - Nightingale, Peter AU - Stergiou, Kostas T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 138 EP - 142 UR - https://ijcai.org/proceedings/2005/73 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
