Analysis of Core-Guided MaxSat Using Cores and Correction Sets

Nina Narodytska, Nikolaj S. BjørnerSAT 2022 · DOI

TL;DR

This paper bridges a gap in understanding core-guided MAXSAT solvers by demonstrating that the "cores" they implicitly discover share crucial properties with those explicitly extracted by other state-of-the-art solvers (MaxHS). This finding suggests a deeper theoretical connection between different MAXSAT solving paradigms and opens avenues for using these discovered cores as certificates for optimal solutions.

What Problem Does This Paper Address?

Maximum Satisfiability (MAXSAT) is a fundamental problem in computer science with applications ranging from software engineering to planning. Solving MAXSAT involves finding an assignment to Boolean variables that satisfies the maximum number of given clauses, especially when the entire set of clauses is unsatisfiable. Two prominent families of MAXSAT solvers exist: MaxHS, which leverages minimum hitting set computations on unsatisfiable cores, and core-guided solvers, which iteratively relax the problem to increase lower bounds on the optimal solution. While MaxHS solvers have well-understood theoretical properties related to the cores they discover, the nature and significance of the cores implicitly found by core-guided solvers have remained largely unexplored. This paper aims to bridge this gap by analyzing the properties of these implicitly discovered cores and their relationship to the optimization objective.

Methods

The authors analyze the behavior of core-guided solvers, specifically the PM₁ algorithm, by examining the "cores" and "correction sets" they implicitly generate during their execution. They introduce the concept of a "core structure" (p-cores) for core-guided solvers, analogous to the core structure (h-cores) in MaxHS. The paper then rigorously proves that these p-cores exhibit properties similar to h-cores, including:

  • Completeness: The discovered cores, when taken together, can potentially represent all minimal unsatisfiable cores (MUSes) of the original problem.
  • MINHS-monotonicity: The size of the minimum hitting set of the discovered cores increases monotonically throughout the solving process.
  • Optimality Certificate: The minimum hitting set of the final set of discovered cores provides an optimal solution to the MAXSAT problem.

They achieve this by defining and analyzing "meta-traces" and "cover structures" of the intermediate relaxed formulas generated by PM₁, and relating them back to the original problem's cores and correction sets.

Datasets

Not discussed in the paper. The paper uses a running example (Example 7) and other illustrative examples to demonstrate its theoretical findings, rather than relying on standard datasets for empirical evaluation.

Key Insights and Ideas

  • Unified View of MAXSAT Solvers: The paper establishes a strong theoretical link between MaxHS and core-guided solvers by showing that their implicitly and explicitly discovered cores share fundamental properties. This suggests that these different algorithmic approaches are exploring the problem's structure in a related manner.
  • Cores as Certificates: The discovered cores from core-guided solvers can serve as an "optimality certificate," similar to how minimum hitting sets function in MaxHS. This is a significant theoretical contribution, as it provides a concrete output from core-guided solvers that directly relates to the optimal solution.
  • Covers of Metas are Powerful: The analysis highlights that "covers of metas" (collections of intermediate relaxed formulas) are more informative than individual metas. These covers exhibit stronger properties and are crucial for proving the key theoretical results.
  • Practical Implications for Optimization: The findings suggest that by analyzing these discovered cores, one might be able to optimize the solving process, for instance, by compressing cardinality constraints or improving the minimization procedure.

Key Results

The paper proves that the core structure discovered by core-guided solvers (p-cores) satisfies the same three key properties (completeness, MINHS-monotonicity, and optimality certificate) as the core structure discovered by MaxHS solvers (h-cores). Specifically:

  • Theorem 11 & 17: Establish that for both MaxHS and PM₁, the final set of discovered cores provides an optimality certificate.
  • Lemma 26 & Theorem 27: Demonstrate that the size of the minimum hitting set of cores in a cover is at least the number of cardinality constraints relevant to that cover, supporting the MINHS-monotonicity property.
  • Proposition 31: Shows that under certain conditions, the extracted minimum correction sets from covers of metas are exhaustive.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Generalization to Other Solvers: While the analysis is primarily on PM₁, the authors discuss how their core extraction algorithm could be adapted for other core-guided solvers like RC2 and PMRES. However, they note that certain properties relied upon in their proofs might not hold for these solvers, requiring further investigation.
  • Computational Cost of Core Extraction: The procedure for extracting minimal cores from solutions of cardinality constraints can be computationally expensive, especially as the number of solutions grows exponentially.
  • Practical Efficiency: Future work will focus on how these theoretical properties can be leveraged to speed up MAXSAT solving in practice. This includes developing more efficient heuristics for enumerating solutions or subsets of solutions, and exploring strategies for compressing core structures.
  • Guiding the Search: Investigating how the discovered cores can better guide the search procedure, for example, by choosing between growing a single cover or multiple disjoint covers, is another promising avenue.

Summary updated

BibTeX
@inproceedings{narodytska2022analysis,
  author = {Nina Narodytska and Nikolaj S. Bjørner},
  title = {{Analysis of Core-Guided MaxSat Using Cores and Correction Sets}},
  booktitle = {SAT},
  year = {2022},
  doi = {10.4230/lipics.sat.2022.26},
}
Figure