We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Towards Faster Conflict-Driven Pseudo-Boolean Solving

00:00

Formale Metadaten

Titel
Towards Faster Conflict-Driven Pseudo-Boolean Solving
Serientitel
Anzahl der Teile
28
Autor
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
The last 20 years have seen dramatic improvements in the performance of algorithms for Boolean satisfiability---so-called SAT solvers---and today conflict-driven clause learning (CDCL) solvers are routinely used in a wide range of application areas. One serious short-coming of CDCL, however, is that the underlying method of reasoning is quite weak. A tantalizing solution is to instead use stronger pseudo-Boolean (PB) reasoning (a.k.a. 0-1 integer linear programming), but so far the promise of exponential gains in performance has mostly failed to materialize---the increased theoretical strength seems hard to harness algorithmically, and in many applications CDCL-based methods are still superior. In this talk, we will discuss conflict-driven search and how to lift it from clauses to pseudo-Boolean linear constraints. We will survey the "classic" method in [Chai and Kuehlmann '05] based on saturation, and then describe a relatively new approach from [Elffers and Nordström '18] instead using division. We will also try to highlight some of the obstacles that remain along the path to truly efficient pseudo-Boolean solvers.