Completion of Disjunctive Logic Programs

Mario Alviano, Carmine DodaroIJCAI 2016

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.

Performance comparison across benchmarks: (a) Cactus plot of execution times; (b-d) Scatter plots comparing the new linear completion and propagator against traditional shift-based methods.

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

BibTeX
@inproceedings{alviano2016completion,
  author = {Mario Alviano and Carmine Dodaro},
  title = {{Completion of Disjunctive Logic Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure