DROPS

Artifact

Dataset

ML-KULeuven/SAT25_PB_reductions_experiments

Authors: Orestis Lomis, Jo Devriendt, Hendrik Bierlee, and Tias Guns

Abstract

Cite as

Orestis Lomis, Jo Devriendt, Hendrik Bierlee, Tias Guns. ML-KULeuven/SAT25_PB_reductions_experiments (Dataset, Experimental Results). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24089,
   title = {{ML-KULeuven/SAT25\underlinePB\underlinereductions\underlineexperiments}}, 
   author = {Lomis, Orestis and Devriendt, Jo and Bierlee, Hendrik and Guns, Tias},
   note = {Dataset, This research was partly funded by the European Research Council (ERC) under the EU Horizon 2020 research and innovation programme (Grant No 101002802, CHAT-Opt)., swhId: \href{https://archive.softwareheritage.org/swh:1:dir:650c2f9b37926504a59a11a6dbf319620b311dc3;origin=https://github.com/ML-KULeuven/SAT25_PB_reductions_experiments;visit=swh:1:snp:c9843bb9ce4bf323c83b69edd5820bdb654e19be;anchor=swh:1:rev:d5b602b4b96833a077bd379b2803314349cb8548}{\texttt{swh:1:dir:650c2f9b37926504a59a11a6dbf319620b311dc3}} (visited on 2025-08-07)},
   url = {https://github.com/ML-KULeuven/SAT25_PB_reductions_experiments},
   doi = {10.4230/artifacts.24089},
}

Document

DOI: 10.4230/LIPIcs.SAT.2025.21

Improving Reduction Techniques in Pseudo-Boolean Conflict Analysis

Authors: Orestis Lomis, Jo Devriendt, Hendrik Bierlee, and Tias Guns

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract

Recent pseudo-Boolean (PB) solvers leverage the cutting planes proof system to perform SAT-style conflict analysis during search. This process learns implied PB constraints, which can prune later parts of the search tree and is crucial to a PB solver’s performance. A key step in PB conflict analysis is the reduction of a reason constraint, which caused a variable propagation that contributed to the conflict. While necessary, reduction generally makes the reason constraint less strong. Consequently, different approaches to reduction have been proposed, broadly categorised as division- or saturation-based, with the aim of preserving the strength of the reason constraint as much as possible. This paper proposes two novel techniques in each reduction category. We theoretically show how each technique yields reason constraints which are at least as strong as those obtained from existing reduction methods. We then evaluate the empirical effectiveness of the reduction techniques on hard knapsack instances and the most recent PB'24 competition benchmarks.

Cite as

Orestis Lomis, Jo Devriendt, Hendrik Bierlee, and Tias Guns. Improving Reduction Techniques in Pseudo-Boolean Conflict Analysis. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lomis_et_al:LIPIcs.SAT.2025.21,
  author =	{Lomis, Orestis and Devriendt, Jo and Bierlee, Hendrik and Guns, Tias},
  title =	{{Improving Reduction Techniques in Pseudo-Boolean Conflict Analysis}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.21},
  URN =		{urn:nbn:de:0030-drops-237551},
  doi =		{10.4230/LIPIcs.SAT.2025.21},
  annote =	{Keywords: Constraint Programming, Pseudo-Boolean Reasoning, Conflict Analysis}
}

Search Results

Documents authored by Lomis, Orestis

ML-KULeuven/SAT25_PB_reductions_experiments

Abstract

Cite as

Improving Reduction Techniques in Pseudo-Boolean Conflict Analysis

Abstract

Cite as

Thanks for your feedback!

Could not send message