Inductive definitions in constraint programming

Rehan Abdul Aziz, Peter J. Stuckey, Zoltan Somogyi

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

Constraint programming (CP) and answer set programming (ASP) are two declarative paradigms used to solve combinatorial problems. Many modern solvers for both these paradigms rely on partial or complete Boolean representations of the problem to exploit the extremely efficient techniques that have been developed for solving propositional satisfiability problems. This convergence on a common representation makes it possible to incorporate useful features of CP into ASP and vice versa. There has been significant effort in recent years to integrate CP into ASP, primarily to overcome the grounding bottleneck in traditional ASP solvers that exists due to their inability to handle integer variables efficiently. On the other hand, ASP solvers are more efficient than CP systems on problems that involve inductive definitions, such as reachability in a graph. Besides efficiency, ASP syntax is more natural and closer to the mathematical definitions of such concepts. In this paper, we describe an approach that adds support for answer set rules to a CP system, namely the lazy clause generation solver chuffed. This integration also naturally avoids the grounding bottleneck of ASP since constraint solvers natively support finite domain variables. We demonstrate the usefulness of our approach by comparing our new system against two competitors: the state-of-the-art ASP solver clasp, and clingcon, a system that extends clasp with CP capabilities.

Original languageEnglish
Title of host publicationComputer Science 2013 - Proceedings of the 36th Australasian Computer Science Conference, ACSC 2013
EditorsBruce Thomas
PublisherAustralian Computer Society Inc
Pages41-50
Number of pages10
ISBN (Electronic)9781921770203
Publication statusPublished - 1 Jan 2013
Externally publishedYes

Publication series

NameConferences in Research and Practice in Information Technology Series
Volume135
ISSN (Print)1445-1336

Keywords

  • Answer set programming
  • Constraint programming
  • Inductive definitions
  • Stable model semantics

Cite this