Boosting MCSes Enumeration

Éric Grégoire, Yacine Izza, Jean-Marie LagniezIJCAI 2018 · DOI

TL;DR

This paper introduces a novel technique, "model rotation," to significantly speed up the enumeration of Maximal Correction Subsets (MCSes) for unsatisfiable Boolean formulas. By efficiently exploring the space of potential MCSes, their method outperforms existing state-of-the-art approaches, making it more practical for complex AI problems.

What Problem Does This Paper Address?

In Artificial Intelligence, particularly in areas like model-based diagnosis and belief revision, we often encounter situations where a set of logical constraints (a CNF formula) is contradictory, meaning it's unsatisfiable. To reason about such situations, we need to identify subsets of these constraints that are "maximal satisfiable" (MSSes) or, conversely, "minimal correction subsets" (MCSes). An MCS is a minimal set of clauses that, if removed, would make the entire formula satisfiable. While finding a single MCS is a well-studied problem, enumerating all MCSes is computationally challenging because their number can be exponential in the worst case. Existing methods, while effective, can still be too slow for large or complex problems. This paper aims to improve the efficiency of enumerating all MCSes.

Methods

The core contribution of this paper is the introduction of a "model rotation paradigm" to boost MCS enumeration. This paradigm is integrated into an existing framework that uses "selectors" (fresh literals added to clauses) to track which clauses are active or inactive. The authors build upon the "Enhanced Linear Search" (ELS) algorithm, which iteratively finds MCSes and adds "blocking clauses" to prevent re-finding the same MCS.

The key novelties include:

  • Recursive Model Rotation (RMR): This technique, adapted from MUS enumeration, helps discover multiple "transition clauses" (TCes) – clauses that, if removed, make a previously unsatisfiable formula satisfiable. By systematically "rotating" models and exploring the implications of these TCes, the algorithm can identify multiple MCSes more efficiently than brute-force methods.
  • TC-MCS Algorithm: This recursive algorithm leverages RMR to enumerate MCSes. It works by identifying TCes and then recursively calling itself on subproblems, effectively exploring different branches of the MCS search space.
  • Integration with Caching: The proposed approach is shown to be compatible with caching techniques, which store previously computed results to avoid redundant computations. Combining RMR with caching leads to further performance gains.

Datasets

The authors evaluated their algorithms on a combination of benchmarks:

  • 866 benchmarks from [Previti et al., 2017; Marques-Silva et al., 2013], consisting of 269 plain Max-SAT instances and 597 Partial-Max-SAT instances.
  • An additional set of 1090 benchmarks, including 493 plain Max-SAT instances and 597 Partial-Max-SAT instances, sourced from the MUS competition.

Key Insights and Ideas

  • The Power of Transition Clauses: Identifying transition clauses is crucial. These clauses act as pivot points, allowing us to systematically explore different MCSes.
  • Model Rotation as a Search Strategy: The model rotation paradigm provides an efficient way to explore the solution space by systematically flipping variable assignments and identifying new TCes. This is more effective than simply trying to find one MCS at a time and blocking it.
  • Duality of MUSes and MCSes: The paper leverages insights from MUS enumeration, highlighting the underlying connections between these related problems.
  • Practical Implications for AI: Faster MCS enumeration has direct benefits for AI tasks that rely on reasoning with contradictory information, such as diagnosis and belief revision.

Key Results

The experimental results demonstrate significant improvements:

  • Enum-ELS-RMR vs. Enum-ELS: The proposed algorithm with model rotation (Enum-ELS-RMR) consistently computed more (or the same number of) MCSes compared to the baseline Enhanced Linear Search (Enum-ELS) on both Max-SAT and Partial-Max-SAT benchmarks.
  • Enum-ELS-RMR-Cache: Combining model rotation with caching (Enum-ELS-RMR-Cache) further boosted performance, finding a larger number of MCSes for most instances.
  • Outperforming State-of-the-Art: Enum-ELS-RMR-Cache significantly outperformed the state-of-the-art mcscache-els tool, especially for instances with a large number of MCSes.
  • Memory Considerations: While performance improved, the caching approach sometimes led to more memory-out conclusions, suggesting that managing the cache size is an important factor.

Limitations and Future Work

  • Practical Efficiency of RMR: The authors note that while the RMR process is theoretically polynomial, it can be time-consuming in practice, especially when the set of blocking clauses becomes large. They propose strategies to mitigate this.
  • Completeness of RMR: The RMR process for finding TCes is described as "incomplete," meaning it might not find all possible TCes.
  • Future Directions: The authors suggest several avenues for future research:
  • Parallelization of the enumeration task using Property 3.
  • Extending RMR with local search techniques to detect more TCes.
  • Adapting the approach to enumerate "preferred MCSes" based on pre-ordering of clauses.
  • Leveraging improved MSS/MCS enumeration for skeptical reasoning in AI.

Summary updated

BibTeX
@inproceedings{gregoire2018boosting,
  author = {Éric Grégoire and Yacine Izza and Jean-Marie Lagniez},
  title = {{Boosting MCSes Enumeration}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/182},
}
Figure