Unifying Core-Guided and Implicit Hitting Set Based Optimization

Hannes Ihalainen, Jeremias Berg, Matti JärvisaloIJCAI 2023 · DOI

TL;DR

This paper introduces UNIMAXSAT, a novel algorithmic framework that unifies two prominent approaches to solving complex optimization problems: core-guided (CG) and implicit hitting set (IHS). By abstracting the core concepts of these methods, UNIMAXSAT provides a unified theoretical foundation and enables the development of new, potentially more efficient, algorithmic variants.

What Problem Does This Paper Address?

Many real-world AI problems, such as those in maximum satisfiability (MaxSAT), require finding optimal solutions to computationally hard optimization tasks. Two dominant algorithmic paradigms for tackling these problems are core-guided (CG) and implicit hitting set (IHS) approaches. While both rely on iteratively finding "unsatisfiable cores" using SAT solvers, they differ significantly in how they process these cores. This leads to varying performance across different problem types, and the fundamental reasons for these differences are not well understood. The paper aims to bridge this gap by providing a unifying framework that captures the essence of both CG and IHS, offering a common ground for understanding their strengths and weaknesses, and facilitating the creation of new algorithms.

Methods

The core contribution is the UNIMAXSAT framework, built upon the concept of "abstract cores" and "abstraction sets."

  • Abstraction Sets (AB): These are generalized representations of constraints, defined by input literals, output literals, and a satisfiable CNF formula. They capture properties of the problem more compactly than traditional cores.
  • Abstract Cores: These are clauses entailed by the problem's definitions and feasible abstraction sets. They can involve both original objective variables and the outputs of abstraction sets.
  • Abstract Candidates: These are partial assignments that can be extended to minimum-cost solutions of abstract cores. This notion is central to the framework's ability to prune the search space.

The UNIMAXSAT framework (Algorithm 3) iteratively refines a set of abstraction sets (AB) and abstract cores (K). In each step, it computes an abstract candidate (γA) and uses an "EX-ABSCORE" subroutine to check for a solution to the original problem. If no solution is found, a new abstract core is derived, added to K, and new abstraction sets are added to AB. The framework's correctness is proven under certain assumptions about its subroutines, which can be instantiated to represent existing CG and IHS algorithms.

The paper also details how existing algorithms like OLL (a core-guided algorithm) and basic IHS can be viewed as instantiations of UNIMAXSAT. Furthermore, it proposes a new core-guided variant called ABSTCG, which handles cores with variables having different coefficients in the objective function by partitioning the core and introducing abstraction sets for each partition.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic framework and its theoretical underpinnings, with empirical evaluation presented as a comparison of runtime performance between OLL and the proposed ABSTCG on existing weighted MaxSAT instances.

Key Insights and Ideas

  • Unified Abstraction: The concept of "abstract cores" and "abstraction sets" provides a powerful, generalized way to represent the information captured by both CG and IHS methods, moving beyond the specifics of clause-based cores.
  • Bridging the Gap: UNIMAXSAT offers a common theoretical language to understand and prove the correctness of diverse MaxSAT algorithms, potentially explaining performance differences between CG and IHS.
  • Algorithmic Generation: The framework is not just descriptive but generative. By instantiating its components, new algorithmic variants can be systematically designed and their correctness formally established.
  • ABSTCG: A Novel Variant: The proposed ABSTCG algorithm demonstrates the practical utility of the framework by introducing a new approach to handle complex cores, showing competitive performance against a strong existing algorithm.

Key Results

  • Theoretical Unification: The paper presents a general algorithmic framework (UNIMAXSAT) that unifies core-guided and implicit hitting set MaxSAT algorithms.
  • Correctness Proofs: The framework provides a uniform method for establishing the correctness of various unsatisfiability-based MaxSAT algorithms by showing they are instantiations of UNIMAXSAT.
  • New Algorithm Design: The framework facilitated the design and implementation of a novel core-guided algorithm, ABSTCG.
  • Empirical Validation: A prototype implementation of ABSTCG was compared against OLL on 607 weighted MaxSAT instances from the MaxSAT Evaluation 2022. For the 237 instances where ABSTCG was heuristically invoked, it solved 125 instances compared to OLL's 124, demonstrating its competitiveness and potential for practical use. ABSTCG achieved at least a 2x speedup on 13 instances, while OLL was faster on only 4.

Limitations and Future Work

  • Heuristic Instantiation: The paper acknowledges that the effectiveness of UNIMAXSAT in practice relies on the specific heuristics used in its subroutines (e.g., how abstract candidates are chosen, how abstraction sets are added). The performance of the proposed ABSTCG is based on a heuristic for deciding when to use it.
  • Generalization: While the framework is presented for MaxSAT, its applicability to other constraint optimization paradigms (like pseudo-Boolean optimization, finite-domain constraint optimization, and answer set programming) is mentioned as a future direction.
  • Further Algorithmic Exploration: The paper suggests that further exploration of different instantiations of UNIMAXSAT could lead to even more efficient and novel algorithms for MaxSAT and related problems. The empirical results of ABSTCG suggest that novel algorithmic instantiations can be practically interesting.

Summary updated

BibTeX
@inproceedings{ihalainen2023unifying,
  author = {Hannes Ihalainen and Jeremias Berg and Matti Järvisalo},
  title = {{Unifying Core-Guided and Implicit Hitting Set Based Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/215},
}
Figure