Abstract
In Answer Set Programming (ASP), translating disjunctive logic programs into propositional formulas typically requires a "shift" transformation that is quadratic in the size of rule heads. This paper introduces a linear-sized completion method ($comp^\lor$) and a specialized propagator for the WASP solver. These contributions eliminate the quadratic bottleneck, significantly reducing memory usage and improving performance on benchmarks with large disjunctions.
Introduction
Clark’s completion is a cornerstone technique in ASP, enabling the translation of logic programs into Conjunctive Normal Form (CNF) for processing by SAT solvers. While this process is linear for standard programs, disjunctive programs—where rules like $a \lor b \leftarrow c$ allow multiple outcomes—traditionally require a preliminary "shift" step.
The shift transformation is quadratic relative to the number of atoms in a rule's head. While manageable for small heads, modern ASP grounders often produce rules with thousands of atoms. In such scenarios, the quadratic blow-up leads to prohibitive memory consumption, often causing solvers to crash before the search phase begins.
Methodology
The authors propose two primary solutions to bypass the quadratic bottleneck:
1. Linear Completion ($comp^\lor$)
A new construction for the completion of disjunctive programs is defined that remains linear ($O(n)$) relative to the program size. This is achieved by introducing auxiliary atoms representing suffixes of the disjunction and tracking specific "support" states for each atom. This approach ensures a compact CNF representation while correctly identifying supported models.
2. Ad-hoc Propagator
To further optimize performance, a specialized propagator was implemented within the WASP solver. Instead of generating a massive set of static clauses, this propagator uses pseudo-Boolean constraints to dynamically manage disjunctive support logic. This method is more memory-efficient and leverages the solver's internal unit resolution more effectively.
Experimental Evaluation
The proposed methods were evaluated against state-of-the-art solvers (like CLASP) and traditional shift-based approaches across three benchmarks:
- ASP Competition Instances: Modified to include unbounded disjunctions.
- Minimal Hitting Set (MHS): A problem naturally characterized by large disjunctions.
- Synthetic Scaling Benchmark: Designed to test limits with up to 30,000+ atoms in a single rule head.
Key Results
The experimental results demonstrate the robustness and efficiency of the linear approach. In synthetic tests, traditional solvers crashed at 30,000 atoms due to memory exhaustion, whereas the linear completion and propagator maintained steady, linear memory growth.
On the MHS benchmark, the WASP solver with the new propagator outperformed competing configurations on hard instances. Furthermore, in the ASP competition benchmark, the number of solved instances for WASP increased from 74 to 79 by adopting the linear completion method.
Conclusion
The "shift" transformation represents a significant practical barrier for modern ASP applications involving large disjunctions. By providing a linear-sized completion and an efficient propagator, this work enables solvers to handle previously intractable programs. Future work will explore integrating these techniques with unfounded set inference to further enhance performance on non-tight programs.
Summary updated