Fast SAT-based Answer Set Solver

Zhijun Lin, Yuanlin Zhang, Hector HernandezAAAI 2006

Abstract

Modern Answer Set Programming (ASP) solvers often leverage propositional satisfiability (SAT) engines. However, for non-tight programs, standard SAT solvers may find models that are not valid answer sets. This paper introduces SAG, a high-performance ASP solver that integrates "answer set extensibility checking" directly into the inner loop of a SAT solver. By pruning the search space early using partial assignments and loop formulas, SAG achieves significant speedups over existing "generate and test" approaches.

Introduction

Answer Set Programming (ASP) is a declarative paradigm well-suited for complex combinatorial search problems. While SAT solvers provide a powerful underlying engine for ASP, a fundamental challenge arises with "non-tight" programs—those containing circular dependencies. In these cases, a SAT solver's model might violate the stability requirements of answer set semantics.

Traditional solvers like ASSAT and CMODELS employ a "generate and test" strategy: the SAT solver finds a complete model, which is then verified against loop formulas. If verification fails, a constraint is added, and the search restarts. This approach is often inefficient, as the solver may spend significant time exploring branches that could be invalidated much earlier.

The SAG Solver: A "Clear-Box" Approach

SAG addresses this inefficiency by moving answer set checking into the SAT solver's inner loop. Instead of waiting for a complete model, SAG periodically evaluates partial assignments to ensure they can still lead to a valid answer set.

Algorithm and Implementation

The core of SAG is the ASP_deduce function, which is invoked during the SAT search. It utilizes the Atmost operator to determine if a partial truth assignment is extensible.

Algorithm 1: The core loop of the SAG solver, integrating answer set checking into the SAT search process.

When a partial assignment is found to be non-extensible, SAG identifies the specific "active" loop formulas being violated. These are converted into inferred clauses and integrated into the SAT solver's conflict-learning mechanism. This allows the solver to prune entire subtrees of the search space that cannot lead to valid answer sets.

To balance the computational cost, SAG employs a heuristic invocation probability ($p$). The solver only runs the extensibility check at a given decision level with probability $p$. SAG was implemented by modifying the MChaff SAT solver, inheriting its efficient conflict-driven clause learning (CDCL) capabilities.

Experimental Evaluation

The authors evaluated SAG against several state-of-the-art solvers, including SMODELS (SM), CMODELS (CM), and ASSAT. Benchmarks included:

  • Hamiltonian Circuit (HC): Finding paths in various graph types (random, simplex, hand-coded).
  • Bounded LTL Model Checking (BMC): Standard problems from BMC competitions.
  • Automaton Requirements: Verification tasks for deterministic automata.

All logic programs were grounded using LPARSE prior to solving.

Key Results and Discussion

Experimental results demonstrate that SAG consistently outperforms its predecessors, often by one to two orders of magnitude on difficult benchmarks.

Table 4: Performance comparison on Hamiltonian Circuit benchmarks for hand-coded graphs.

As shown in Table 4, on the sim7 graph, SAG (with $p=0.5$) completed the task in 0.06 seconds, whereas SMODELS required over 513 seconds. Furthermore, SAG exhibited greater robustness; while other solvers frequently timed out (indicated by **), SAG successfully found solutions across most instances.

An important finding was the impact of the invocation probability $p$. While $p=0.5$ provides more frequent pruning, a lower probability like $p=0.1$ was often more effective. This suggests that even occasional guidance from loop formulas is sufficient to steer the SAT solver away from unproductive regions of the search space without incurring excessive overhead.

Conclusion

SAG represents a significant advancement in SAT-based ASP solving. By transforming loop formulas into learned clauses during the search process, it leverages the strengths of modern SAT technology while adhering strictly to answer set semantics. Future work includes refining the invocation heuristics and addressing potential grounding bottlenecks in extremely large-scale applications.

Summary updated

BibTeX
@inproceedings{lin2006fast,
  author = {Zhijun Lin and Yuanlin Zhang and Hector Hernandez},
  title = {{Fast SAT-based Answer Set Solver}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure