›› 2012, Vol. 27 ›› Issue (1): 37-41.doi: 10.1007/s11390-012-1204-5

• Artificial Intelligent and Pattern Recognition • Previous Articles     Next Articles

Integrating Standard Dependency Schemes in QCSP Solvers

Ji-Wei Jin1 (金继伟), Fei-Fei Ma2 (马菲菲), Member, ACM and Jian Zhang3 (张健), Senior Member, CCF, ACM, IEEE   

  1. State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China
  • Received:2011-07-01 Revised:2011-10-17 Online:2012-01-05 Published:2012-01-05
  • Supported by:

    This work is supported in part by the National Natural Science Foundation of China under Grant No. 61070039.

Quantified constraint satisfaction problems (QCSPs) are an extension to constraint satisfaction problems (CSPs) with both universal quantifiers and existential quantifiers. In this paper we apply variable ordering heuristics and integrate standard dependency schemes in QCSP solvers. The technique can help to decide the next variable to be assigned in QCSP solving. We also introduce a new factor into the variable ordering heuristics: a variable's dep is the number of variables depending on it. This factor represents the probability of getting more candidates for the next variable to be assigned. Experimental results show that variable ordering heuristics with standard dependency schemes and the new factor dep can improve the performance of QCSP solvers.

[1] Nightingale P. Consistency and the quantified constraint sati-sfaction problem [PhD thesis]. School of Computer Science,St Andrews University, 2007.

[2] Nightingale P. Non-binary quantified CSP: Algorithms andmodelling. Constraints, 2009, 14(4): 539-581.

[3] Stynes D. Value ordering for offine and realtime-online solv-ing of quantified constraint satisfaction problem [PhD thesis].Department of Computer Science, National University of Ire-land, 2009.

[4] Gent I P, Nightingale P, Stergiou K. QCSP-Solve: A solverfor quantified constraint satisfaction problems. In Proc. Int.Joint. Conf. Artificial Intelligence (IJCAI), Edinburgh, UK,July 30-August 5, 2005, pp.138-143.

[5] Gent I P, Nightingale P, Rowley A, Stergiou K. Solving quan-tified constraint satisfaction problems. Artif. Intell., 2008,172(6-7): 738-771.

[6] Verger G, Bessiere C. Blocksolve: A bottom-up approachfor solving quantified CSPs. In Proc. CP, Nantes, France,September 25-29, 2006, pp.635-649.

[7] Benedetti M, Lallouet A, Vautard J. Reusing CSP propaga-tors for QCSPs. In Proc. CSCLP, Caparica, Portugal, June26-28, 2006, pp.63-77.

[8] Bessi?ere C, R?egin J C. MAC and combined heuristics: Tworeasons to forsake FC (and CBJ?) on hard problems. In Proc.CP, Cambridge, USA, August 19-22, 1996, pp.61-75.

[9] Stynes D, Brown K N. Value ordering for quantified CSPs.Constraints, 2009, 14(1): 16-37.

[10] Bacchus F, Stergiou K. Solution directed backjumping forQCSP. In Proc. CP, Providence, USA, September 23-27,2007, pp.148-163.

[11] Lonsing F, Biere A. Integrating dependency schemes insearch-based QBF solvers. In Proc. SAT, Edinburgh, UK,July 11-14, 2010, pp.158-171.

[12] Bubeck U. Model-based transformations for quantifiedboolean formulas [Dissertations]. In Artificial Intelligent,Vol.329, Bibel W (eds.), IOS Press/Academische Verlagsgesellschaft AKA, Amsterdam NL Heidelberg DE, 2010.

[13] Bubeck U, Kleine B?uning H. Bounded universal expansionfor preprocessing QBF. In Proc. SAT, Lisbon, Portugal, May28-31, 2007, pp.244-257.

[14] Samer M. Variable dependencies of quantifed CSPs. In Proc.Logic for Programming, Artificial Intelligence, and Reason-ing, Doha, Qatar, November 22-27, 2008, pp.512-527.

[15] Samer M, Szeider S. Backdoor sets of quantified boolean for-mulas. J. Autom. Reasoning, 2009, 42(1): 77-97.

[16] Rossi F, van Beek P, Walsh T. Handbook of Constraint Pro-gramming, Elsevier. 2006.

[17] Dechter R, Meiri I. Experimental evaluation of preprocessingalgorithms for constraint satisfaction problems. Artif. Intell.,1994, 68(2): 211-241.

[18] Frost D, Dechter R. Look-ahead value ordering for constraintsatisfaction problems. In Proc. Int. Joint. Conf. ArtificialIntelligence (IJCAI), Montreal, Canada, August 20-25, 1995,pp.572-578.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved