Depth-Driven Circuit-Level Stochastic Local Search for SAT

Belov, Anton; Järvisalo, Matti; Stachniak, Zbigniew

doi:10.5591/978-1-57735-516-8/IJCAI11-092

Depth-Driven Circuit-Level Stochastic Local Search for SAT

Anton Belov, Matti Järvisalo, Zbigniew Stachniak

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 504-508.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-092

Abstract

We develop a novel circuit-level stochastic local search (SLS) method D-CRSat for Boolean satisfiability by integrating a structure-based heuristic into the recent CRSat algorithm. D-CRSat significantly improves on CRSat on real-world application benchmarks on which other current CNF and circuit-level SLS methods tend to perform weakly. We also give an intricate proof of probabilistically approximate completeness for D-CRSat, highlighting key features of the method.

Anton Belov, Matti Järvisalo, and Zbigniew Stachniak. 2011. Depth-Driven Circuit-Level Stochastic Local Search for SAT. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 504–508. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-092

@inproceedings{ijcai2011p92,
  title     = {Depth-Driven Circuit-Level Stochastic Local Search for SAT},
  author    = {Belov, Anton and Järvisalo, Matti and Stachniak, Zbigniew},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {504--508},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-092},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-092},
}

TY  - CPAPER
TI  - Depth-Driven Circuit-Level Stochastic Local Search for SAT
AU  - Belov, Anton
AU  - Järvisalo, Matti
AU  - Stachniak, Zbigniew
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 504
EP  - 508
DO  - 10.5591/978-1-57735-516-8/IJCAI11-092
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-092
ER  -