Loop Formulas for Logic Programs with Arbitrary Constraint Atoms

Jia-Huai You, Guohua LiuAAAI 2008

Abstract

Modern Answer Set Programming (ASP) faces significant challenges when integrating complex aggregates and global constraints. Traditional methods often rely on exponential "unfolding" of these constraints into simple logic rules, leading to computational bottlenecks. This paper, originally presented at AAAI 2008, introduces a generalized framework for loop formulas that accommodates arbitrary constraint atoms (c-atoms). By extending the theoretical foundations of loop formulas and leveraging Pseudo-Boolean (PB) solvers, the authors provide a path toward more compact and efficient logic programming systems that bridge the gap between ASP and Constraint Programming (CP).

Introduction

Answer Set Programming (ASP) has emerged as a powerful paradigm for solving combinatorial search problems. However, its practical application has historically been limited by the difficulty of handling "aggregates" (e.g., SUM, COUNT) and "global constraints" (e.g., AllDifferent). While constraint atoms (c-atoms) were introduced to represent these complex relations, computing their stable models—or answer sets—remained a significant hurdle.

The standard approach to solving logic programs involves translating them into propositional logic. For programs containing loops (circular dependencies), this translation requires "loop formulas" to eliminate models that lack grounded support. Previous research successfully defined loop formulas for specific constraint types, such as monotone or convex constraints. This paper generalizes this concept, providing a universal loop formula applicable to any arbitrary constraint atom.

Methodology

The authors' approach is rooted in the semantics of conditional satisfaction and involves three primary theoretical and practical components: Local Power Sets, Generalized Loop Formulas, and Pseudo-Boolean Encoding.

Local Power Sets (LPS)

To represent the admissible solutions of a c-atom compactly, the authors introduce the concept of Local Power Sets (LPS). By identifying "maximal" LPSs, the framework can represent complex constraints more efficiently than a simple enumeration of every possible solution. This serves as the foundation for defining how constraints interact within the program's dependency structure.

Generalized Loop Formulas

The paper defines a new dependency graph, denoted as $G_P^a$, which accounts for the dependencies between atoms within a constraint's head and those in its body. Based on this graph, the authors formulate a generalized loop formula ($LP^a(L)$). This formula ensures that any set of atoms forming a loop is only considered true if it possesses "external support"—meaning it is justified by atoms or facts outside that specific circular dependency.

Pseudo-Boolean (PB) Encoding

A critical contribution of this work is the move away from traditional propositional unfolding. Instead of decomposing a constraint into thousands of simple logic rules—which often results in an exponential blow-up in size—the authors propose encoding the program’s completion and loop formulas into Pseudo-Boolean constraints. These are linear inequalities over 0-1 variables, which can be handled natively by efficient PB solvers.

Theoretical Results and Insights

The core of the paper is established in Theorem 2, which proves that for any constraint program $P$, a set of atoms $M$ is an answer set if and only if $M$ is a model of the program's completion combined with the newly defined generalized loop formulas. This result confirms that the proposed formulas correctly capture the stable model semantics for arbitrary constraints.

Compactness and Efficiency

The authors demonstrate that their approach offers significant advantages in terms of representation size:

  • Linear Encoding: Constraints such as COUNT aggregates or AllDifferent can be encoded into a PB theory with a size that is linear ($O(n)$) relative to the number of atoms involved.
  • Universal Applicability: The formulas work for monotone, antimonotone, and non-monotone constraints. Interestingly, for simpler monotone or convex cases, these new formulas are often exponentially smaller than those proposed in earlier literature.
  • Solving Power: By referencing the pigeon-hole problem, the authors highlight that PB solvers can solve certain unsatisfiable problems in polynomial time. In contrast, standard ASP solvers relying on resolution-like methods often require exponential time for the same problems.

Discussion and Future Directions

This work represents a foundational step in integrating the modeling flexibility of ASP with the solving efficiency of Constraint Programming. By identifying PB solvers as the "missing link," the authors provide a blueprint for a new generation of solvers that avoid the pitfalls of exponential grounding.

However, the paper remains primarily theoretical. While it establishes the mathematical validity of the approach, it does not present a fully realized implementation or empirical benchmarks against contemporary solvers like clingo. Future work is required to develop practical systems that automatically generate these PB encodings and to investigate how PB solver heuristics can be optimized for the specific structures generated by ASP loop formulas. Ultimately, this research paves the way for incorporating global constraints directly into ASP, potentially transforming how complex combinatorial problems are modeled and solved.

Summary updated

BibTeX
@inproceedings{you2008loop,
  author = {Jia-Huai You and Guohua Liu},
  title = {{Loop Formulas for Logic Programs with Arbitrary Constraint Atoms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure