Maximum Satisfiability Using Cores and Correction Sets
Abstract
Core-guided MAXSAT algorithms dominate other methods in solving industrial MAXSAT problems. In this work, we propose a new efficient algorithm that is guided by correction sets and cores. At every iteration, the algorithm obtains a correction set or a core, which is then used to rewrite the formula using incremental and succinct transformations. We theoretically show that correction sets and cores have complementary strengths and empirically demonstrate that their combination leads to an efficient MAXSAT solver that outperforms state-of-the-art WPMS solvers on the 2014 Evaluation on industrial instances.
Cite
Text
Bjørner and Narodytska. "Maximum Satisfiability Using Cores and Correction Sets." International Joint Conference on Artificial Intelligence, 2015.Markdown
[Bjørner and Narodytska. "Maximum Satisfiability Using Cores and Correction Sets." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/bjrner2015ijcai-maximum/)BibTeX
@inproceedings{bjrner2015ijcai-maximum,
title = {{Maximum Satisfiability Using Cores and Correction Sets}},
author = {Bjørner, Nikolaj S. and Narodytska, Nina},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {246-252},
url = {https://mlanthology.org/ijcai/2015/bjrner2015ijcai-maximum/}
}