TY - GEN

T1 - Inductive definitions in constraint programming

AU - Aziz, Rehan Abdul

AU - Stuckey, Peter J.

AU - Somogyi, Zoltan

PY - 2013/1/1

Y1 - 2013/1/1

N2 - 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.

AB - 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.

KW - Answer set programming

KW - Constraint programming

KW - Inductive definitions

KW - Stable model semantics

UR - http://www.scopus.com/inward/record.url?scp=85002891658&partnerID=8YFLogxK

M3 - Conference Paper

AN - SCOPUS:85002891658

T3 - Conferences in Research and Practice in Information Technology Series

SP - 41

EP - 50

BT - Computer Science 2013 - Proceedings of the 36th Australasian Computer Science Conference, ACSC 2013

A2 - Thomas, Bruce

PB - Australian Computer Society Inc

ER -