Abstract Cores in Implicit Hitting Set MaxSat Solving (Extended Abstract)

Jeremias Berg, Fahiem Bacchus, Alex PooleIJCAI 2021 · DOI

TL;DR

This paper introduces "abstract cores" as a more compact way to represent sets of constraints in MaxSAT solving, addressing a bottleneck where traditional methods require an exponential number of core extractions. By integrating abstract core reasoning into existing Implicit Hitting Set (IHS) solvers, the authors achieve state-of-the-art performance, surpassing previous top solvers on benchmark instances.

What Problem Does This Paper Address?

Maximum Satisfiability (MaxSAT) is a crucial problem in artificial intelligence with applications in various optimization tasks. It involves finding an assignment to variables that satisfies the maximum number of constraints in a given formula, where some constraints are "hard" (must be satisfied) and others are "soft" (preferred to be satisfied).

A successful approach to solving MaxSAT is the Implicit Hitting Set (IHS) method. IHS solvers decouple the problem into two main steps:

  1. Core Extraction: A Boolean Satisfiability (SAT) solver identifies "cores" – minimal sets of soft constraints that cannot be simultaneously satisfied along with the hard constraints.
  2. Optimization: An Integer Linear Programming (ILP) solver uses these cores to find a minimum-cost set of soft constraints to violate, thereby finding an optimal MaxSAT solution.

While IHS solvers perform well on many real-world problems, they suffer from a significant drawback: on certain instances, the SAT solver might need to extract an exponential number of individual cores before the ILP solver can determine the optimal solution. This can make the solving process prohibitively slow. This paper aims to address this bottleneck by proposing a more efficient way to represent and reason about these cores.

Methods

The core contribution of this paper is the introduction of abstract cores. Instead of representing a core as a set of specific soft constraints (or their corresponding blocking variables), an abstract core represents a group of constraints. This is achieved by introducing abstraction sets, which are collections of blocking variables that are treated as a unit.

Key aspects of the method include:

  • Abstraction Sets: These sets group blocking variables. For each abstraction set ab, new "count variables" (ab.c[k]) are introduced. These count variables indicate how many variables within the abstraction set ab are set to TRUE (meaning their corresponding soft clauses are falsified).
  • Abstract Cores: An abstract core is a clause that can contain either positive blocking variables or positive count variables. It is entailed by the hard clauses and the definitions of the count variables. The paper demonstrates that a single abstract core can be equivalent to a potentially exponential number of traditional (non-abstract) cores.
  • Abstract-IHS Algorithm: The authors extend the standard IHS algorithm to incorporate abstract core reasoning. This involves:
  • Modifying the ILP optimization problem to consider both abstract and regular cores, along with the definitions of count variables.
  • Enhancing the ex-cores procedure (which extracts cores) to use abstraction sets and extract abstract cores.
  • Maintaining and dynamically updating a collection of abstraction sets during the search.
  • Abstraction Set Refinement: The paper discusses a practical approach to forming abstraction sets. They are clustered based on the weights of blocking variables and how often they appear together in extracted cores. This clustering is refined dynamically if the solver's progress stalls.

Datasets

The paper evaluates their approach on instances from the MaxSAT Evaluation 2019 (MSE 2019). They used all 599 weighted and 586 unweighted instances from the complete track of this evaluation. These instances are drawn from various problem families. No new benchmarks were introduced.

Key Insights and Ideas

  • Abstraction as a Compact Representation: The most significant insight is that abstract cores provide a powerful way to compress information. Instead of listing every single constraint that must be avoided, we can abstractly state that "at least k out of this group of n variables must be true." This is crucial for instances where the specific identity of violated constraints doesn't matter as much as the number of them.
  • Bridging the Exponential Gap: Abstract cores directly address the exponential core extraction bottleneck in IHS solvers. By representing many traditional cores with a single abstract core, the SAT solver's workload is drastically reduced.
  • Synergy of SAT and ILP: The approach effectively leverages the strengths of both SAT solvers (for core extraction) and ILP solvers (for optimization). Abstract cores allow the SAT solver to communicate more complex information to the ILP solver in a more concise format.
  • Dynamic Abstraction Set Management: The idea of dynamically refining abstraction sets based on solver performance is a practical innovation. It acknowledges the trade-off between the overhead of abstraction and its benefits, allowing the algorithm to adapt.

Key Results

The experimental evaluation shows that integrating abstract core reasoning significantly improves the performance of IHS solvers:

  • The proposed solver, maxhs-abs, increased the number of solved unweighted instances from 397 to 433 and weighted instances from 361 to 379 compared to the base maxhs solver.
  • This performance improvement allowed maxhs-abs to surpass other top solvers like rc2 and UWr on the MSE 2019 benchmarks.
  • A further enhancement, maxhs-abs-ex (which includes core exhaustion techniques), achieved even better results, solving 438 unweighted and 387 weighted instances.
  • The paper notes that maxhs-abs-ex also performed exceptionally well in the 2020 MSE, indicating the robustness of the abstract core approach.

Limitations and Future Work

  • Overhead of Abstraction: The paper acknowledges a trade-off: while abstract cores can reduce the number of cores, creating and managing large abstraction sets can introduce overhead. If abstraction sets are too small, the algorithm reverts to non-abstract IHS; if they are too large, the CNF encoding of count variable definitions can become inefficient.
  • Practical Implementation: The authors mention that their implementation uses specific encodings for count variables (totalizer encoding) and clustering algorithms (Louvain). Further research could explore alternative encodings and clustering strategies.
  • Future Work: The paper suggests that the abstract core approach has the potential to be applied to other related problems beyond MaxSAT. Further exploration of different abstraction strategies and their impact on performance is also a natural direction.

Summary updated

BibTeX
@inproceedings{berg2021abstract,
  author = {Jeremias Berg and Fahiem Bacchus and Alex Poole},
  title = {{Abstract Cores in Implicit Hitting Set MaxSat Solving (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/643},
}
Figure