Introduction
In the domain of over-constrained Boolean systems, identifying Minimal Correction Subsets (MCSes) is a fundamental task with applications ranging from software debugging to hardware configuration. Traditional approaches have long relied on clause-based reasoning, which often struggles as the number of constraints grows. This research introduces a paradigm shift: the Literal-Based eXtractor (LBX). By pivoting from clause-centric to literal-centric reasoning, LBX achieves significant performance gains, particularly on complex, "hard" instances.
Problem Statement
Over-constrained systems are sets of constraints that cannot be simultaneously satisfied. Resolving these conflicts involves finding:
- Maximal Satisfiable Subsets (MSS): The largest subsets of constraints that remain satisfiable.
- Minimal Correction Subsets (MCS): The smallest subsets of constraints whose removal restores satisfiability.
The computational cost of finding an MCS is typically tied to the number of clauses ($m$). In modern SAT problems, $m$ often vastly exceeds the number of variables ($|X|$), creating a performance bottleneck for traditional clause-based algorithms.
The LBX Algorithm
The core innovation of LBX is the theoretical link between an MCS and the "backbone" of its corresponding MSS. A backbone consists of literals that must maintain a specific truth value in every model of a formula. LBX leverages this by asking whether a literal belongs to the backbone, rather than whether a clause belongs to the correction set.
Technical Advantages
- Reduced Complexity: By tying query complexity to the number of variables ($O(|X|)$) instead of clauses ($O(m)$), LBX scales more effectively for "tall" formulas.
- Incremental SAT Solving: The algorithm utilizes incremental SAT solvers and "assumptions," avoiding the overhead of creating new Boolean variables for each clause.
- MaxSAT Approximation: LBX extends to MaxSAT through literal selection heuristics, stratified extraction, and search space pruning, allowing it to find high-quality approximate solutions rapidly.
Experimental Evaluation
The authors benchmarked LBX against state-of-the-art solvers (CMP, RS, CLD) using three datasets: ijcai13-bench, mus-bench, and a newly curated maxsat-bench containing 179 "hard" instances where existing solvers struggled.
Results and Discussion
As shown in Table 1, LBX significantly outperforms its predecessors on the most challenging instances. On the maxsat-bench dataset, LBX solved 138 instances, compared to 103 by the next best solver, CMP.
The cactus plot in Figure 1 further illustrates this efficiency. LBX remains competitive with the Virtual Best Solver (VBS) across a wide range of instances, demonstrating both speed and scalability. Beyond raw extraction speed, LBX proved highly effective for MaxSAT approximation. Under a strict 60-second time limit, it frequently matched or exceeded the solution quality of dedicated MaxSAT solvers like Dist and WPM.
Conclusion
LBX represents a significant advancement in MCS extraction by shifting the focus to literal-based reasoning. Its variable-centric complexity makes it uniquely suited for modern, constraint-heavy SAT problems. Future work includes refining literal selection heuristics and exploring the application of this paradigm to SMT and CSP domains.
Summary updated