Abstract
In this paper we show that the power of using k-consistency techniques in a constraint problem is precisely captured by using a particular inference rule, which we call positive-hyper-resolution, on the direct Boolean encoding of the CSP instance. We also show that current clause-learning SAT-solvers will deduce any positive-hyper-resolvent of a fixed size from a given set of clauses in polynomial expected time. We combine these two results to show that, without being explicitly designed to do so, current clause-learning SAT-solvers efficiently simulate k-consistency techniques, for all values of k. We then give some experimental results to show that this feature allows clause-learning SAT-solvers to efficiently solve certain families of CSP instances which are challenging for conventional CP solvers.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G12/MiniZinc constraint solver. Software, http://www.g12.cs.mu.oz.au/minizinc/download.html
MiniSat solver. Software, http://minisat.se/MiniSat.html
2nd internat. CSP solver competition, http://www.cril.univ-artois.fr/CPAI06/
3rd international CSP solver competition, http://cpai.ucc.ie/08/
Atserias, A., Fichte, J.K., Thurley, M.: Clause-learning algorithms with many restarts and bounded-width resolution. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 114–127. Springer, Heidelberg (2009)
Atserias, A., Bulatov, A.A., Dalmau, V.: On the power of k-consistency. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 279–290. Springer, Heidelberg (2007)
Atserias, A., Dalmau, V.: A combinatorial characterization of resolution width. Journal of Computer and Systems Science 74(3), 323–334 (2008)
Bacchus, F.: GAC Via Unit Propagation. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 133–147. Springer, Heidelberg (2007)
Barto, L., Kozik, M.: Constraint satisfaction problems of bounded width. In: Proceedings of FOCS 2009, pp. 595–603. IEEE Computer Society, Los Alamitos (2009)
Beame, P., Kautz, H.A., Sabharwal, A.: Towards understanding and harnessing the potential of clause learning. Journal of Artificial Intelligence Research 22, 319–351 (2004)
Bessiére, C.: Constraint propagation. In: Handbook of Constraint Programming, ch. 3, pp. 29–83. Elsevier, Amsterdam (2006)
Bordeaux, L., Hamadi, Y., Zhang, L.: Propositional satisfiability and constraint programming: A comparative survey. ACM Computing Surveys 38(4) (2006)
Cooper, M.C.: An optimal k-consistency algorithm. Artificial Intelligence 41, 89–95 (1989)
Cooper, M.C., Cohen, D.A., Jeavons, P.G.: Characterising tractable constraints. Artificial Intelligence 65, 347–361 (1994)
Deville, Y., Barette, O., van Hentenryck, P.: Constraint satisfaction over connected row convex constraints. In: Proceeedings of IJCAI 1997, pp. 405–411 (1997)
Freuder, E.C.: Synthesizing constraint expressions. ACM Comm. 21, 958–966 (1978)
Gent, I., Jefferson, C., Miguel, I.: Minion: A fast scalable constraint solver. In: Proceeedings of ECAI 2006, pp. 98–102. IOS Press, Amsterdam (2006)
Hwang, J., Mitchell, D.: 2-way vs. d-way branching for CSP. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 343–357. Springer, Heidelberg (2005)
Rish, I., Dechter, R.: Resolution versus search: Two strategies for SAT. Journal of Automated Reasoning 24(1/2), 225–275 (2000)
Kolaitis, P.G., Vardi, M.Y.: A game-theoretic approach to constraint satisfaction. In: Proceedings of AAAI 2000, pp. 175–181 (2000)
Mackworth, A.K.: Consistency in networks of relations. Artificial Intelligence 8, 99–118 (1977)
Montanari, U.: Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences 7, 95–132 (1974)
Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an efficient SAT solver. In: International Design Automation Conference, DAC, pp. 530–535 (2001)
Petke, J., Jeavons, P.G.: Tractable benchmarks for constraint programming. Technical Report RR-09-07, Computing Laboratory, University of Oxford (2009)
Pipatsrisawat, K., Darwiche, A.: On the power of clause-learning SAT solvers with restarts. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 654–668. Springer, Heidelberg (2009)
Walsh, T.: SAT v CSP. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 441–456. Springer, Heidelberg (2000)
Tamura, N., Taga, A., Kitagawa, S., Banbara, M.: Compiling finite linear CSP into SAT. Constraints 14(2), 254–272 (2009)
Zhang, L., Madigan, C.F., Moskewicz, M.W., Andmalik, S.: Efficient conflict driven learning in a Boolean satisfiability solver. In: Proceedings of the International Conference on Computer-Aided Design (ICCAD 2001), pp. 279–285 (2001)
Zhang, L., Malik, S.: The quest for efficient Boolean satisfiability solvers. In: Brinksma, E., Larsen, K.G. (eds.) CAV 2002. LNCS, vol. 2404, pp. 641–653. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Petke, J., Jeavons, P. (2010). Local Consistency and SAT-Solvers. In: Cohen, D. (eds) Principles and Practice of Constraint Programming – CP 2010. CP 2010. Lecture Notes in Computer Science, vol 6308. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15396-9_33
Download citation
DOI: https://doi.org/10.1007/978-3-642-15396-9_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15395-2
Online ISBN: 978-3-642-15396-9
eBook Packages: Computer ScienceComputer Science (R0)