Inductive Denitions in Constraint Programming

Aziz, R.A., Stuckey, P.J. and Somogyi, Z.

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 cling-con, a system that extends clasp with CP capabilities.

Cite as: Aziz, R.A., Stuckey, P.J. and Somogyi, Z. (2013). Inductive Denitions in Constraint Programming. In Proc. Computer Science 2013 (ACSC 2013) Adelaide, Australia. CRPIT, 135. Thomas, B. Eds., ACS. 41 - 50

(from crpit.com) (local if available)