Introduction
Modern SAT solvers are highly optimized for finding total assignments in propositional logic. However, many real-world problems involving reachability or recursive properties are more naturally expressed using Inductive Definitions (ID). While solvers like MiniSAT(ID) handle these PC(ID) theories, they often expend significant effort on "irrelevant" variables. Traditional solvers typically search for a total assignment, but in many cases, a partial assignment is sufficient to prove a theory's satisfaction. This paper introduces the formal concept of relevance to identify variables that actually contribute to justifying a theory, allowing solvers to ignore unnecessary branches and stop early.
Methodology: Justifications and Relevance
The authors' approach is grounded in the concept of justifications—directed graphs that map how the truth of a literal is derived from others within an inductive definition.
- Defining Relevance: A literal is considered relevant if it can still influence the justification of the theory's root goal ($p_T$). If a variable's value no longer impacts whether the theory is satisfied (e.g., a disjunction is already satisfied by another literal), it becomes irrelevant.
- Heuristic Integration: The standard VSIDS (Variable State Independent Decaying Sum) branching heuristic was modified to restrict its choices to the set of currently relevant literals.
- Early Stopping: The solver was updated to terminate as soon as a sufficient justification for the root goal is found, even if many variables remain unassigned.
These techniques were implemented within the MiniSAT(ID) solver, part of the IDP3 knowledge representation system.
Experimental Evaluation
The researchers evaluated the relevance-aware solver against standard benchmarks from Answer Set Programming (ASP) competitions, including Hamiltonian Path, N-Queens, Sokoban, and Stable Marriage. They also developed a custom "Hard" problem encoding designed to trap standard solvers in irrelevant but computationally expensive sub-problems (specifically, a pigeonhole problem).
Key Findings on Search Efficiency
A primary insight is that the state-of-the-art VSIDS heuristic is often "relevance-blind." In the Stable Marriage problem, for instance, over 96% of decisions made by a standard solver were found to be irrelevant to the final justification. By focusing only on relevant literals, the solver can significantly prune the search space.
As shown in the cactus plot above, the relevance-aware solver (R) consistently requires fewer decisions across a wide range of problem instances compared to the non-relevance (NR) version.
Performance on Constrained Problems
The most dramatic improvements were observed in the custom-crafted "Hard" problem. In this scenario, the standard VSIDS heuristic was forced to resolve a difficult but irrelevant sub-problem, whereas the relevance-aware heuristic bypassed it entirely.
The table above highlights the efficiency gains: decisions dropped from approximately 10.3 million to 150,000, and total running time was reduced by nearly two-thirds. Notably, the percentage of irrelevant decisions ($irr^d$) and conflicts ($irr^c$) dropped to zero with the new approach.
Discussion and Future Work
While the reduction in search space is significant, the current implementation faces challenges with computational overhead. Calculating the set of relevant literals at every step is expensive; in some cases, such as Graceful Graphs, the bookkeeping costs outweighed the search benefits. Furthermore, the current theory is limited to PC(ID) and does not yet support language extensions like aggregates or arithmetic.
Future research will focus on engineering more efficient algorithms for tracking relevance and exploring its application in native ASP solvers and lazy grounding contexts, where avoiding unnecessary variable generation is critical.
Summary updated