Unifying Core-Guided and Implicit Hitting Set Based Optimization
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.
Cite
Text
Ihalainen et al. "Unifying Core-Guided and Implicit Hitting Set Based Optimization." International Joint Conference on Artificial Intelligence, 2023. doi:10.24963/IJCAI.2023/215Markdown
[Ihalainen et al. "Unifying Core-Guided and Implicit Hitting Set Based Optimization." International Joint Conference on Artificial Intelligence, 2023.](https://mlanthology.org/ijcai/2023/ihalainen2023ijcai-unifying/) doi:10.24963/IJCAI.2023/215BibTeX
@inproceedings{ihalainen2023ijcai-unifying,
title = {{Unifying Core-Guided and Implicit Hitting Set Based Optimization}},
author = {Ihalainen, Hannes and Berg, Jeremias and Järvisalo, Matti},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2023},
pages = {1935-1943},
doi = {10.24963/IJCAI.2023/215},
url = {https://mlanthology.org/ijcai/2023/ihalainen2023ijcai-unifying/}
}