Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-20T09:20:54.007Z Has data issue: false hasContentIssue false
  • English
  • Français

ASP modulo CSP: The clingcon system

Published online by Cambridge University Press:  05 September 2012

MAX OSTROWSKI  and
TORSTEN SCHAUB
MAX OSTROWSKI
Affiliation:
Institut für Informatik, Universität Potsdam
TORSTEN SCHAUB
Affiliation:
Institut für Informatik, Universität Potsdam
Get access Rights & Permissions [Opens in a new window]

Abstract

We present the hybrid ASP solver clingcon, combining the simple modeling language and the high performance Boolean solving capacities of Answer Set Programming (ASP) with techniques for using non-Boolean constraints from the area of Constraint Programming (CP). The new clingcon system features an extended syntax supporting global constraints and optimize statements for constraint variables. The major technical innovation improves the interaction between ASP and CP solver through elaborated learning techniques based on irreducible inconsistent sets. A broad empirical evaluation shows that these techniques yield a performance improvement of an order of magnitude.

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 12 , Issue 4-5: 28th International Conference on Logic Programming , July 2012 , pp. 485 - 503
Copyright
Copyright © Cambridge University Press 2012

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

ASP Competition. 2011. https://www.mat.unical.it/aspcomp2011/.Google Scholar
Balduccini, M. 2009. Representing constraint satisfaction problems in answer set programming. In Workshop ASPOCP'09.Google Scholar
Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press.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
Biere, A., Heule, M., van Maaren, H. and Walsh, T., 2009. Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications. IOS Press.Google Scholar
Bofill, M., Nieuwenhuis, R., Oliveras, A., Rodríguez-Carbonell, E. and Rubio, A. 2008. The barcelogic SMT solver. In Computer Aided Verification. Springer, 294–298.CrossRefGoogle Scholar
Chinneck, J. and Dravinieks, E. 1991. Locating minimal infeasible constraints sets in linear programs. In ORSA Journal On Computing 3, 157–168.CrossRefGoogle Scholar
clingcon. http://www.cs.uni-potsdam.de/clingcon.Google Scholar
Dal Palù, A., Dovier, A., Pontelli, E. and Rossi, G. 2009. Answer set programming with constraints using lazy grounding. See Hill and Warren (2009), 115–129.Google Scholar
Dechter, R. 2003. Constraint Processing. Morgan Kaufmann Publishers.Google Scholar
Drescher, C. and Walsh, T. 2010. A translational approach to constraint answer set solving. In TPLP, vol. 10(4–6). Cambridge University Press, 465–480.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T. and Thiele, S. A user's guide to gringo, clasp, clingo, and iclingo. Available at http://potassco.sourceforge.net.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T., Schneider, M. and Ziller, S. 2011. A portfolio solver for answer set programming: Preliminary report. In Proceedings of LPNMR'11. Springer, 352–357.Google Scholar
Gebser, M., Kaminski, R. and Schaub, T. 2011. Complex optimization in answer set programming: Extended version. Unpublished draft. Available at (metasp).CrossRefGoogle Scholar
Gebser, M., Kaufmann, B., Neumann, A. and Schaub, T. 2007. 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. See Hill and Warren (2009), 235–249.Google Scholar
gecode. http://www.gecode.org.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385.CrossRefGoogle Scholar
Hill, P. and Warren, D., Eds. 2009. Proceedings of ICLP'09. Springer.Google Scholar
Janhunen, T., Liu, G. and Niemelä, I. 2011. Tight integration of non-ground answer set programming and satisfiability modulo theories. In Proceedings of GTTV'11. 1–13.Google Scholar
Junker, U. 2001. QuickXPlain: Conflict detection for arbitrary constraint propagation algorithms. IJCAI'01 Workshop on Modelling and Solving Problems with Constraints.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
metasp. http://www.cs.uni-potsdam.de/metasp.Google Scholar
Mohr, R. and Henderson, T. 1986. Arc and path consistency revisited. Artificial Intelligence 28, 2, 225–233.CrossRefGoogle Scholar
Niemelä, I. 2008. Stable models and difference logic. Annals of Mathematics and Artificial Intelligence 53, 1–4, 313–329.CrossRefGoogle Scholar
Nieuwenhuis, R., Oliveras, A. and Tinelli, C. 2006. Solving SAT and SMT: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T). JACM 53, 6, 937–977.CrossRefGoogle Scholar
Schulte, C., Tack, G. and Lagerkvist, M. 2012. Modeling. In Modeling and Programming with Gecode, Schulte, C., Tack, G., and Lagerkvist, M.. Corresponds to Gecode 3.7.2.Google Scholar
Syrjänen, T. Lparse 1.0 user's manual. http://www.tcs.hut.fi/Software/smodels/lparse.ps.gz.Google Scholar
Tamura, N., Tanjo, T. and Banbara, M. 2008. System description of a SAT-based CSP solver Sugar. In Third International CSP Solver Competition. 71–75.Google Scholar
van Loon, J. 1981. Irreducibly inconsistent systems of linear inequalities. In European Journal of Operational Research. vol. 3. Elsevier Science, 283–288.Google Scholar
Yu, Y. and Malik, S. 2006. Lemma learning in SMT on linear constraints. In Theory and Applications of Satisfiability Testing - SAT 2006. Springer, 142–155.CrossRefGoogle Scholar