License: Creative Commons Attribution 4.0 International 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
Go to the corresponding LIPIcs Volume Portal

Smirnov, Pavel ; Berg, Jeremias ; Järvisalo, Matti

Pseudo-Boolean Optimization by Implicit Hitting Sets

LIPIcs-CP-2021-51.pdf (1 MB)


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

  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 =		{},
  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
Collection: 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): archived at:

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI