From Sampling to Model Counting

Gomes, Carla P.; Hoffmann, Jörg; Sabharwal, Ashish; Selman, Bart

From Sampling to Model Counting

Carla P. Gomes, Jörg Hoffmann, Ashish Sabharwal, Bart Selman

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2293-2298.

Abstract

We introduce a new technique for counting models of Boolean satisfiability problems. Our approach incorporates information obtained from sampling the solution space. Unlike previous approaches, our method does not require uniform or near-uniform samples. It instead converts local search sampling without any guarantees into very good bounds on the model count with guarantees. We give a formal analysis and provide experimental results showing the effectiveness of our approach.

Carla P. Gomes, Jörg Hoffmann, Ashish Sabharwal, and Bart Selman. 2007. From Sampling to Model Counting. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07. IJCAI, 2293–2298. https://ijcai.org/proceedings/2007/369

@inproceedings{ijcai2007p369,
  title     = {From Sampling to Model Counting},
  author    = {Gomes, Carla P. and Hoffmann, Jörg and Sabharwal, Ashish and Selman, Bart},
  booktitle = {Proceedings of the Twentieth International Joint Conference on
               Artificial Intelligence, {IJCAI-07}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ramon López de Mántaras},
  pages     = {2293--2298},
  year      = {2007},
  url       = {https://ijcai.org/proceedings/2007/369},
}

TY  - CPAPER
TI  - From Sampling to Model Counting
AU  - Gomes, Carla P.
AU  - Hoffmann, Jörg
AU  - Sabharwal, Ashish
AU  - Selman, Bart
T2  - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2007
SP  - 2293
EP  - 2298
UR  - https://ijcai.org/proceedings/2007/369
ER  -