Using combinatorial benchmarks to probe the reasoning power of pseudo-boolean solvers

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Abstract

We study cdcl-cuttingplanes, Open-WBO, and Sat4j, three successful solvers from the Pseudo-Boolean Competition 2016, and evaluate them by performing experiments on crafted benchmarks designed to be trivial for the cutting planes (CP) proof system underlying pseudo-Boolean (PB) proof search but yet potentially tricky for PB solvers. Our experiments demonstrate severe shortcomings in state-of-the-art PB solving techniques. Although our benchmarks have linear-size tree-like CP proofs, and are thus extremely easy in theory, the solvers often perform quite badly even for very small instances. We believe this shows that solvers need to employ stronger rules of cutting planes reasoning. Even some instances that lack not only Boolean but also real-valued solutions are very hard in practice, which indicates that PB solvers need to get better not only at Boolean reasoning but also at linear programming. Taken together, our results point to several crucial challenges to be overcome in the quest for more efficient pseudo-Boolean solvers, and we expect that a further study of our benchmarks could shed more light on the potential and limitations of current state-of-the-art PB solving.

Detaljer

Författare
Externa organisationer
  • KTH Royal Institute of Technology
  • Tata Institute of Fundamental Research
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Titel på värdpublikationTheory and Applications of Satisfiability Testing – SAT 2018
Undertitel på gästpublikation21st International Conference, SAT 2018, Held as Part of the Federated Logic Conference, FloC 2018, Proceedings
RedaktörerOlaf Beyersdorff, Christoph M. Wintersteiger
FörlagSpringer
Sidor75-93
Antal sidor19
ISBN (tryckt)9783319941431
StatusPublished - 2018
PublikationskategoriForskning
Peer review utfördJa
Externt publiceradJa
Evenemang21st International Conference on Theory and Applications of Satisfiability Testing, SAT 2018 Held as Part of the Federated Logic Conference, FloC 2018 - Oxford, Storbritannien
Varaktighet: 2018 jul 92018 jul 12

Publikationsserier

NamnLecture Notes in Computer Science
FörlagSpringer
Volym10929
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349

Konferens

Konferens21st International Conference on Theory and Applications of Satisfiability Testing, SAT 2018 Held as Part of the Federated Logic Conference, FloC 2018
LandStorbritannien
OrtOxford
Period2018/07/092018/07/12