Certified CNF Translations for Pseudo-Boolean Solving

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 1,56 MB, PDF-dokument

The dramatic improvements in Boolean satisfiability (SAT) solving since the turn of the millennium have made it possible to leverage state-of-the-art conflict-driven clause learning (CDCL) solvers for many combinatorial problems in academia and industry, and the use of proof logging has played a crucial role in increasing the confidence that the results these solvers produce are correct. However, the fact that SAT proof logging is performed in conjunctive normal form (CNF) clausal format means that it has not been possible to extend guarantees of correctness to the use of SAT solvers for more expressive combinatorial paradigms, where the first step is an unverified translation of the input to CNF. In this work, we show how cutting-planes-based reasoning can provide proof logging for solvers that translate pseudo-Boolean (a.k.a. 0-1 integer linear) decision problems to CNF and then run CDCL. To support a wide range of encodings, we provide a uniform and easily extensible framework for proof logging of CNF translations. We are hopeful that this is just a first step towards providing a unified proof logging approach that will also extend to maximum satisfiability (MaxSAT) solving and pseudo-Boolean optimization in general.

OriginalsprogEngelsk
Titel25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022
RedaktørerKuldeep S. Meel, Ofer Strichman
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato2022
Artikelnummer16
ISBN (Elektronisk)9783959772426
DOI
StatusUdgivet - 2022
Begivenhed25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022 - Haifa, Israel
Varighed: 2 aug. 20225 aug. 2022

Konference

Konference25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022
LandIsrael
ByHaifa
Periode02/08/202205/08/2022
SponsorArtificial Intelligence Journal, CAS Merlin, RenYing Technology, SAT Association for the Financial and Organizational
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind236
ISSN1868-8969

Bibliografisk note

Funding Information:
Funding Stephan Gocht: Swedish Research Council grant 2016-00782. Ruben Martins: National Science Foundation award CCF-1762363 and Amazon Research Award. Jakob Nordström: Swedish Research Council grant 2016-00782 and Independent Research Fund Denmark grant 9040-00389B. Andy Oertel: Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

Publisher Copyright:
© Stephan Gocht, Ruben Martins, Jakob Nordström, and Andy Oertel.

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 342673285