Introduction
In complex systems—ranging from software debugging to hardware fault diagnosis and large-scale ontology management—we often encounter "overconstrained" scenarios where a set of rules or constraints cannot be simultaneously satisfied. To resolve these inconsistencies, researchers identify Minimal Correction Subsets (MCSes): the smallest sets of constraints whose removal restores system satisfiability.
In their AAAI 2018 paper, Alessandro Previti, Carlos Mencía, Matti Järvisalo, and Joao Marques-Silva introduced Premise Set Caching, a novel technique designed to accelerate the enumeration of these fixes by memoizing logical building blocks.
The Challenge of MCS Enumeration
The standard approach to finding MCSes involves repeatedly querying a Boolean Satisfiability (SAT) solver to determine if a specific subset of constraints is satisfiable. Given that SAT solving is NP-complete, these calls are the primary computational bottleneck. In a typical run, an algorithm might execute thousands of nearly identical queries.
Previous optimization efforts focused on "unsatisfiable core caching," which stores entire sets of conflicting constraints to avoid redundant proofs of failure. However, these cores are often large and highly specific to a particular search state. The authors identified that caching the reasons why specific variables are forced to take certain values—rather than just the fact that a whole set is broken—could yield broader benefits.
Premise Set Caching
The researchers introduced Premise Set (PS) Caching and integrated it into the LBX (Literal-Based eXtractor) algorithm.
What is a Premise Set?
A premise set $P$ is a subset of clauses that logically entails a specific literal $l$ (denoted $P \models l$). If the clauses in $P$ are satisfied, $l$ must necessarily be true. By caching these implications, the algorithm can skip expensive SAT solver calls.
Implementation and Integration
The authors developed a lightweight implementation using a "clause-PS occurrence list." This allows for extremely fast cache lookups: to check if a premise set $P$ is active, the algorithm only needs to verify that none of the clauses in $P$ are currently falsified.
LBX is particularly well-suited for this technique because it naturally identifies "backbone" literals—literals that must be true in any valid solution. When the SAT solver discovers a new backbone literal, the algorithm extracts the corresponding premise set and adds it to the cache for future use.
Experimental Evaluation
The approach was evaluated using 811 "hard" benchmark instances from hardware verification and automated reasoning. The primary metric was the number of MCSes enumerated within a 1800-second time limit.
Key Results
The empirical results demonstrate that Premise Set Caching provides a substantial performance boost:
- Direct Improvement: As shown in the comparison between standard LBX and LBX with PS caching, the caching mechanism consistently allows the algorithm to find more MCSes within the same time frame.
- Superiority over Core Caching: LBX with PS caching (LBX-CACHE) outperformed the previous state-of-the-art "core caching" approach (ELS) on the vast majority of benchmarks.
- High Efficiency: Cache hit rates reached up to 90% in many instances, effectively eliminating 9 out of 10 SAT solver calls.
- Scalability: The lightweight nature of the cache ensured that maintenance overhead remained negligible relative to the computational savings.
Conclusion
Premise Set Caching represents a significant advancement in MCS enumeration. By focusing on atomic logical implications rather than aggregate unsatisfiable cores, the technique achieves remarkable speedups and high hit rates. Future work may explore hybrid caching strategies and sophisticated cache eviction policies to further enhance scalability on even larger datasets.
Summary updated