Literal-Based MCS Extraction

Carlos Mencía, Alessandro Previti, João Marques-SilvaIJCAI 2015

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:

  1. Maximal Satisfiable Subsets (MSS): The largest subsets of constraints that remain satisfiable.
  2. 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.

Table 1: Performance comparison across benchmarks. LBX demonstrates a clear advantage on the hard maxsat-bench dataset.

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.

Figure 1: Cactus plot showing CPU time vs. instances solved. LBX (red) maintains high performance, closely trailing the Virtual Best Solver (VBS).

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

BibTeX
@inproceedings{mencia2015literal,
  author = {Carlos Mencía and Alessandro Previti and João Marques-Silva},
  title = {{Literal-Based MCS Extraction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure