Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T19:45:02.919Z Has data issue: false hasContentIssue false
  • English
  • Français

A translational approach to constraint answer set solving

Published online by Cambridge University Press:  09 July 2010

CHRISTIAN DRESCHER  and
TOBY WALSH
CHRISTIAN DRESCHER
Affiliation:
Vienna University of Technology, Austria
TOBY WALSH
Affiliation:
NICTA and University of New South Wales, Australia
Get access Rights & Permissions [Opens in a new window]

Abstract

We present a new approach to enhancing Answer Set Programming (ASP) with Constraint Processing techniques which allows for solving interesting Constraint Satisfaction Problems in ASP. We show how constraints on finite domains can be decomposed into logic programs such that unit-propagation achieves arc, bound or range consistency. Experiments with our encodings demonstrate their computational impact.

Keywords

answer set programmingconstraint processingdecomposition
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 10 , Special Issue 4-6: 26th International Conference on Logic Programming , July 2010 , pp. 465 - 480
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Balduccini, M. 2009. CR-prolog as a specification language for constraint satisfaction problems. In Proceedings of LPNMR'09. Springer, 402–408.Google Scholar
Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press.CrossRefGoogle Scholar
Baral, C., Chancellor, K., Tran, N., Tran, N., Joy, A., and Berens, M. 2004. A knowledge based approach for representing and reasoning about signaling networks. In Proceedings of ISMB/ECCB'04. 15–22.CrossRefGoogle Scholar
Baselice, S., Bonatti, P., and Gelfond, M. 2005. Towards an integration of answer set and constraint solving. In Proceedings of ICLP'05. Springer, 52–66.Google Scholar
Bessière, C., Katsirelos, G., Narodytska, N., Quimper, C.-G., and Walsh, T. 2009. Decompositions of all different, global cardinality and related constraints. In Proceedings of IJCAI'09. AAAI Press/The MIT Press.Google Scholar
Biere, A., Heule, M., van Maaren, H., and Walsh, T., Eds. 2009. Handbook of Satisfiability. IOS Press.Google Scholar
Crawford, J. M. and Baker, A. B. 1994. Experimental results on the application of satisfiability algorithms to scheduling problems. In Proceedings of AAAI'94. AAAI Press, 1092–1097.Google Scholar
Dal Palù, A., Dovier, A., Pontelli, E., and Rossi, G. 2009. Answer set programming with constraints using lazy grounding. In Proceedings of ICLP'09. Springer, 115–129.Google Scholar
Dechter, R. 2003. Constraint Processing. Morgan Kaufmann.Google Scholar
Dovier, A., Formisano, A., and Pontelli, E. 2005. A Comparison Of Clp(Fd) And Asp Solutions To Np-Complete Problems. In Proceedings of ICLP'05. Springer, 67–82.Google Scholar
Fujita, M., Slaney, J. K., and Bennett, F. 1993. Automatic generation of some results in finite algebra. In Proceedings of IJCAI'93. Morgan Kaufmann, 52–59.Google Scholar
Gebser, M., Hinrichs, H., Schaub, T., and Thiele, S. 2009. Xpanda: A (simple) preprocessor for adding multi-valued propositions to ASP. In Proceedings of WLP'09.Google Scholar
Gebser, M., Kaufmann, B., Neumann, A., and Schaub, T. 2007a. Clasp: A conflict-driven answer set solver. In Proceedings of LPNMR'07. Springer, 260–265.Google Scholar
Gebser, M., Kaufmann, B., Neumann, A., and Schaub, T. 2007b. Conflict-driven answer set solving. In Proceedings of IJCAI'07. AAAI Press/The MIT Press, 386–392.Google Scholar
Gebser, M., Ostrowski, M., and Schaub, T. 2009. Constraint answer set solving. In Proceedings of ICLP'09. Springer, 235–249.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of ICLP'88. MIT Press, 1070–1080.Google Scholar
Gent, I. P. 2002. Arc consistency in SAT. In Proceedings of ECAI'02. IOS Press, 121–125.Google Scholar
Gent, I. P. and Walsh, T. 1999. CSPLIB: A benchmark library for constraints. In Proceedings of CP'99. Springer, 480–481.Google Scholar
Gomes, C. P. and Selman, B. 1997. Problem structure in the presence of perturbations. In Proceedings of AAAI'97. AAAI Press, 221–226.Google Scholar
Heljanko, K. and Niemelä, I. 2003. Bounded LTL model checking with stable models. Theory and Practice of Logic Programming 3, 4–5, 519–550.CrossRefGoogle Scholar
Jaffar, J. and Maher, M. J. 1994. Constraint logic programming: A survey. Journal of Logic Programming 19/20, 503–581.CrossRefGoogle Scholar
Järvisalo, M., Oikarinen, E., Janhunen, T., and Niemelä, I. 2009. A module-based framework for multi-language constraint modeling. In Proceedings of LPNMR'09. Springer, 155–169.Google Scholar
Leconte, M. 1996. A bounds-based reduction scheme for constraints of difference. In CP'96, Second International Workshop on Constraint-based Reasoning, Key West, Florida.Google Scholar
Lee, J. 2005. A model-theoretic counterpart of loop formulas. In Proceedings of IJCAI'05. Professional Book Center, 503–508.Google Scholar
Lifschitz, V. 1999. Answer set planning. In Proceedings of ICLP'99. MIT Press, 23–37.Google Scholar
Mellarkod, V. and Gelfond, M. 2008. Integrating answer set reasoning with constraint solving techniques. In Proceedings of FLOPS'08. Springer, 15–31.Google Scholar
Mellarkod, V., Gelfond, M., and Zhang, Y. 2008. Integrating answer set programming and constraint logic programming. Annals of Mathematics and Artificial Intelligence 53, 1-4, 251–287.CrossRefGoogle Scholar
Mitchell, D. 2005. A SAT solver primer. Bulletin of the European Association for Theoretical Computer Science 85, 112–133.Google Scholar
Niemelä, I. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 3–4, 241–273.CrossRefGoogle Scholar
Nieuwenhuis, R., Oliveras, A., and Tinelli, C. 2006. Solving SAT and SAT modulo theories: From an abstract Davis–Putnam–Logemann–Loveland procedure to DPLL(T). Journal of the ACM 53, 6, 937–977.CrossRefGoogle Scholar
Nogueira, M., Balduccini, M., Gelfond, M., Watson, R., and Barry, M. 2001. An A-prolog decision support system for the space shuttle. In Proceedings of PADL'01. Springer, 169–183.Google Scholar
Petrie, K. E. and Smith, B. M. 2003. Symmetry breaking in graceful graphs. In Proceedings of CP'03. Springer, 930–934.Google Scholar
Rossi, F., van Beek, P., and Walsh, T., Eds. 2006. Handbook of Constraint Programming. Elsevier.Google Scholar
Simons, P., Niemelä, I., and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 1–2, 181–234.CrossRefGoogle Scholar
Tamura, N., Taga, A., Kitagawa, S., and Banbara, M. 2006. Compiling finite linear CSP into SAT. In Proceedings of CP'06. Springer, 590–603.Google Scholar
Walsh, T. 2000. SAT v CSP. In Proceedings of CP'00. Springer, 441–456.Google Scholar
You, J.-H. and Hou, G. 2004. Arc-consistency + unit propagation = lookahead. In Proceedings of ICLP'04. Springer, 314–328.Google Scholar