Unifying Core-Guided and Implicit Hitting Set Based Optimization

Hannes Ihalainen; Jeremias Berg; Matti Järvisalo

IJCAI 2023poster1 citations

Unifying Core-Guided and Implicit Hitting Set Based Optimization

Hannes Ihalainen, Jeremias Berg, Matti Järvisalo

Abstract

Two of the most central algorithmic paradigms implemented in practical solvers for maximum satisfiability (MaxSAT) and other related declarative paradigms for NP-hard combinatorial optimization are the core-guided (CG) and implicit hitting set (IHS) approaches. We develop a general unifying algorithmic framework, based on the recent notion of abstract cores, that captures both CG and IHS computations. The framework offers a unified way of establishing the correctness of variants of the approaches, and can be instantiated in novel ways giving rise to new algorithmic variants of the core-guided and IHS approaches. We illustrate the latter aspect by developing a prototype implementation of an algorithm variant for MaxSAT based on the framework.

Constraint Satisfaction and Optimization: CSO: Constraint optimizationConstraint Satisfaction and Optimization: CSO: SatisfiabiltyConstraint Satisfaction and Optimization: CSO: Solvers and tools

BibTeX

@inproceedings{ijcai2023p215,
  title     = {Unifying Core-Guided and Implicit Hitting Set Based Optimization},
  author    = {Ihalainen, Hannes and Berg, Jeremias and Järvisalo, Matti},
  booktitle = {Proceedings of the Thirty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-23}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Edith Elkind},
  pages     = {1935--1943},
  year      = {2023},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2023/215},
  url       = {https://doi.org/10.24963/ijcai.2023/215},
}