1. Improvements to the Implicit Hitting Set Approach to Pseudo-Boolean Optimization
- Author
-
Smirnov, Pavel, Berg, Jeremias, Järvisalo, Matti, Meel, Kuldeep, Strichman, Ofer, Department of Computer Science, Constraint Reasoning and Optimization research group / Matti Järvisalo, and Helsinki Institute for Information Technology
- Subjects
solution-improving search ,Theory of computation → Constraint and logic programming ,implicit hitting sets ,Mathematics of computing → Combinatorial optimization ,113 Computer and information sciences ,unsatisfiable cores ,pseudo-Boolean optimization ,constraint optimization - Abstract
The development of practical approaches to efficiently reasoning over pseudo-Boolean constraints has recently increasing attention as a natural generalization of Boolean satisfiability (SAT) solving. Analogously, solvers for pseudo-Boolean optimization draw inspiration from techniques developed for maximum satisfiability (MaxSAT) solving. Recently, the first practical solver lifting the implicit hitting set (IHS) approach - one of the most efficient approaches in modern MaxSAT solving - to the realm of PBO was developed, employing a PB solver as a core extractor together with an integer programming solver as a hitting set solver. In this work, we make practical improvements to the IHS approach to PBO. We propose the integration of solution-improving search to the PBO-IHS approach, resulting in a hybrid approach to PBO which makes use of both types of search towards an optimal solution. Furthermore, we explore the potential of different variants of core extraction within PBO-IHS - including recent advances in PB core extraction, allowing for extracting more general PB constraints compared to the at-least-one constraints typically relied on in IHS - in speeding up PBO-IHS search. We show that the empirical efficiency of PBO-IHS - recently shown to outperform other specialized PBO solvers - is further improved by the integration of these techniques., LIPIcs, Vol. 236, 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022), pages 13:1-13:18
- Published
- 2022
- Full Text
- View/download PDF