ApproxASP - a Scalable Approximate Answer Set Counter

Mohimenul Kabir, Flavio O. Everardo, Ankit K. Shukla, Markus Hecher, Johannes Klaus Fichte, Kuldeep S. Meel

Introduction

Answer Set Programming (ASP) is a prominent declarative modeling paradigm used extensively in artificial intelligence for tasks such as planning, configuration, and bio-informatics. While modern ASP solvers like clingo are highly efficient at finding individual answer sets, many applications—particularly those involving probabilistic reasoning—require determining the total number of answer sets, a problem known as #ASP.

Counting answer sets is computationally demanding. For "normal" logic programs, the problem is #P-complete, while for "disjunctive" programs, it escalates to #·coNP-complete. Traditional approaches often rely on exhaustive enumeration or reduction to Boolean Satisfiability (SAT). However, enumeration is infeasible for large solution spaces, and reduction to SAT can cause an exponential blow-up in formula size due to the need for loop formulas.

Methodology: Hashing-Based Counting in ASP

ApproxASP addresses these challenges by adapting the hashing-based counting framework, originally developed for SAT (e.g., ApproxMC), directly into the ASP domain.

XOR Hashing and Theoretical Guarantees

The core mechanism involves adding random parity (XOR) constraints to the logic program. These constraints partition the solution space into smaller "cells." By counting the solutions within a single cell and scaling by the number of cells, the total count can be estimated with $(\epsilon, \delta)$ theoretical guarantees. The authors proved that these XOR constraints do not introduce spurious answer sets, preserving the logical integrity of the original program.

Native XOR Solving with GJE

A significant technical innovation in ApproxASP is the integration of a dedicated Gauss-Jordan Elimination (GJE) propagator within the clingo solver. Rather than treating XOR constraints as standard logical rules, the GJE propagator uses linear algebra to prune the search space efficiently. This "native" handling avoids the overhead of SAT reduction and allows the solver to detect conflicts and assignments that would otherwise be missed.

Experimental Evaluation

The performance of ApproxASP was evaluated against state-of-the-art counters, including ApproxMC, Ganak, and DynASP, using a diverse set of benchmarks.

Datasets

  1. Normal Programs: 1,500 instances derived from classic combinatorial problems like Vertex Cover and Dominating Set.
  2. Disjunctive Programs: 200 instances based on 2QBF problems, representing a higher level of complexity.

Performance Results

The results demonstrate that ApproxASP is uniquely capable of handling complex disjunctive programs. While SAT-based counters like Ganak and ApproxMC failed to solve any disjunctive instances due to the complexity of the reduction, ApproxASP successfully solved 185 out of 200.

Table 1: Performance comparison across normal and disjunctive ASP instances.

On normal programs, ApproxASP proved to be highly competitive with ApproxMC, the leading SAT counter. As shown in the cactus plot below, both solvers exhibit similar scalability, significantly outperforming other specialized ASP counting tools.

Figure 1: Cactus plot comparing CPU time across different solvers for normal programs.

Beyond scalability, ApproxASP demonstrated high empirical accuracy. Although the theoretical confidence ($\delta$) was set to 0.8, the observed average error across instances was only 0.037, far exceeding the theoretical bounds.

Conclusion and Future Work

ApproxASP represents the first scalable approximate counter for ASP with rigorous theoretical guarantees. By lifting hashing techniques from SAT and implementing native XOR propagation, it bypasses the limitations of SAT reduction and exhaustive enumeration.

Future research will focus on optimizing independent support selection for disjunctive programs and further refining the GJE propagator's integration with solver heuristics. These engineering improvements are expected to further enhance the tool's performance on increasingly complex real-world logic programs.

Summary updated

Abstract

Answer Set Programming (ASP) is a framework in artificial intelligence and knowledge representation for declarative modeling and problem solving. Modern ASP solvers focus on the computation or enumeration of answer sets. However, a variety of probabilistic applications in reasoning or logic programming require counting answer sets. While counting can be done by enumeration, simple enumeration becomes immediately infeasible if the number of solutions is high. On the other hand, approaches to exact counting are of high worst-case complexity. In fact, in propositional model counting, exact counting becomes impractical. In this work, we present a scalable approach to approximate counting for answer set programming. Our approach is based on systematically adding XOR constraints to ASP programs, which divide the search space. We prove that adding random XOR constraints partitions the answer sets of an ASP program. In practice, we use a Gaussian elimination-based approach by lifting ideas from SAT to ASP and integrating it into a state of the art ASP solver, which we call ApproxASP. Finally, our experimental evaluation shows the scalability of our approach over the existing ASP systems.
BibTeX
@inproceedings{kabir2022approxasp,
  author = {Mohimenul Kabir and Flavio O. Everardo and Ankit K. Shukla and Markus Hecher and Johannes Klaus Fichte and Kuldeep S. Meel},
  title = {{ApproxASP - a Scalable Approximate Answer Set Counter}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20518},
}
Figure