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.
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.
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