Partial MUS Enumeration

Alessandro Previti, João Marques-SilvaAAAI 2013 · DOI

Abstract

Identifying Minimal Unsatisfiable Subsets (MUSes) is crucial for debugging infeasible Boolean formulas. However, existing "all-or-nothing" enumeration methods often fail on complex problems with an astronomical number of MUSes. This paper introduces EMUS, a novel algorithm designed for partial MUS enumeration. By avoiding the common bottleneck of complete Minimal Correction Subset (MCS) generation, EMUS provides an "anytime" stream of explanations, making it effective for large-scale instances where previous state-of-the-art tools time out.

Introduction

In Boolean Satisfiability (SAT), "unsatisfiable" formulas represent problems with no possible solution. To understand why a formula is broken, researchers look for Minimal Unsatisfiable Subsets (MUSes)—minimal sets of clauses that are themselves unsatisfiable. Removing any single clause from an MUS makes the remaining set satisfiable, making MUSes the fundamental "explanations" for infeasibility.

The primary challenge in MUS enumeration is scale. A single formula can contain millions of MUSes. Traditional tools like CAMUS rely on a two-phase approach: first, find all Minimal Correction Subsets (MCSes), then compute their hitting sets to derive MUSes. This "all-or-nothing" strategy fails when the number of MCSes is too large to compute, resulting in zero output before a timeout. EMUS addresses this by enabling "partial enumeration," providing a steady stream of MUSes even for the most complex problems.

The EMUS Algorithm

The core innovation of EMUS is an iterative approach that breaks the sequential dependency between MCS and MUS discovery. Instead of waiting for a complete set of MCSes, EMUS discovers both MUSes and MCSes simultaneously through a duality loop.

The EMUS algorithm iteratively finds maximal models of a selector formula to extract MUSes or MCSes.

The algorithm operates as follows:

  1. Selector Variables: Each clause $c_i$ in the formula $\mathcal{F}$ is assigned a selector variable $p_i$. A secondary formula $Q$ tracks these variables.
  2. Maximal Models: In each iteration, the algorithm finds a "maximal model" of $Q$. This model identifies a large subformula $\mathcal{F}'$ of the original problem.
  3. Duality Loop:
    • If $\mathcal{F}'$ is unsatisfiable, an MUS extractor (e.g., MUSer) identifies a specific MUS. This MUS is then "blocked" in $Q$ to prevent re-discovery.
  4. If $\mathcal{F}'$ is satisfiable, it represents a Maximal Satisfiable Subset (MSS). Its complement is an MCS, which is also blocked in $Q$.
  5. Anytime Property: By alternating between finding MUSes and MCSes, EMUS can report results almost immediately, fulfilling the requirements of an anytime algorithm.

Evaluation and Results

The authors evaluated EMUS on 377 unsatisfiable instances from SAT competitions and real-world hardware/software model checking benchmarks. The test suite included massive instances, such as wb_4m8s4, which contains over 1.7 million clauses.

The results highlight a significant performance trade-off. While traditional hitting-set dualization (like CAMUS) remains faster for small problems where complete enumeration is feasible, EMUS excels as a "heavy lifter" for hard instances.

Partial enumeration results for EMUS across various benchmarks, showing the number of MUSes found over increasing time intervals.

Key findings include:

  • Success on "Impossible" Instances: Out of 143 instances where CAMUS timed out without finding a single MUS, EMUS successfully extracted multiple MUSes for 130 of them.
  • Scalability: On the rocket_ext.b instance, EMUS found over 66,000 MUSes within a 3,600-second window, whereas previous methods provided no results.
  • Steady Throughput: As shown in the performance table, EMUS maintains a steady output of MUSes over time, allowing users to gain insights even if the full set is never reached.

Conclusion and Future Work

EMUS represents a shift from exhaustive to practical MUS enumeration. By leveraging maximal models as heuristics, the algorithm ensures that tested subformulas are as large as possible, maximizing the chance of hitting an unsatisfiable core.

While EMUS is less efficient for complete enumeration of simple formulas due to the overhead of external MUS extraction, its ability to handle millions of clauses makes it a vital tool for industrial-scale debugging. Future work includes integrating more efficient MCS extraction techniques and exploring methods to generate a "diverse" set of representative MUSes rather than just the first ones encountered.

Summary updated

BibTeX
@inproceedings{previti2013partial,
  author = {Alessandro Previti and João Marques-Silva},
  title = {{Partial MUS Enumeration}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8657},
}

Loading related content...

Figure