Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.51
URN: urn:nbn:de:0030-drops-153429
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15342/
Smirnov, Pavel ; Berg, Jeremias ; Järvisalo, Matti
Pseudo-Boolean Optimization by Implicit Hitting Sets
| pdf-format: |
|
Abstract
Recent developments in applying and extending Boolean satisfiability (SAT) based techniques have resulted in new types of approaches to pseudo-Boolean optimization (PBO), complementary to the more classical integer programming techniques. In this paper, we develop the first approach to pseudo-Boolean optimization based on instantiating the so-called implicit hitting set (IHS) approach, motivated by the success of IHS implementations for maximum satisfiability (MaxSAT). In particular, we harness recent advances in native reasoning techniques for pseudo-Boolean constraints, which enable efficiently identifying inconsistent assignments over subsets of objective function variables (i.e. unsatisfiable cores in the context of PBO), as a basis for developing a native IHS approach to PBO, and study the impact of various search techniques applicable in the context of IHS for PBO. Through an extensive empirical evaluation, we show that the IHS approach to PBO can outperform other currently available PBO solvers, and also provides a complementary approach to PBO when compared to classical integer programming techniques.
BibTeX - Entry
@InProceedings{smirnov_et_al:LIPIcs.CP.2021.51,
author = {Smirnov, Pavel and Berg, Jeremias and J\"{a}rvisalo, Matti},
title = {{Pseudo-Boolean Optimization by Implicit Hitting Sets}},
booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
pages = {51:1--51:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-211-2},
ISSN = {1868-8969},
year = {2021},
volume = {210},
editor = {Michel, Laurent D.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15342},
URN = {urn:nbn:de:0030-drops-153429},
doi = {10.4230/LIPIcs.CP.2021.51},
annote = {Keywords: constraint optimization, pseudo-Boolean optimization, implicit hitting sets}
}
| Keywords: | constraint optimization, pseudo-Boolean optimization, implicit hitting sets | |
| Seminar: | 27th International Conference on Principles and Practice of Constraint Programming (CP 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 15.10.2021 | |
| Supplementary Material: | Software (Source Code and Experiment Data): https://bitbucket.org/coreo-group/pbo-ihs-solver/ archived at: https://archive.softwareheritage.org/swh:1:dir:cb17c95ad7c0b25976387d98840a459491191df2 |
