ML Anthology

From Sampling to Model Counting

Carla P. Gomes, Jörg Hoffmann, Ashish Sabharwal, Bart Selman
IJCAI 2007 pp. 2293-2299
/ijcai/2007/gomes2007ijcai-sampling/

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. URL: http://www.cs.cornell.edu/~sabhar/publications/sampleCountIJCAI07.pdf

PDF Semantic Scholar

Cite

Text

Gomes et al. "From Sampling to Model Counting." International Joint Conference on Artificial Intelligence, 2007.

Markdown

[Gomes et al. "From Sampling to Model Counting." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/gomes2007ijcai-sampling/)

BibTeX

@inproceedings{gomes2007ijcai-sampling,
  title     = {{From Sampling to Model Counting}},
  author    = {Gomes, Carla P. and Hoffmann, Jörg and Sabharwal, Ashish and Selman, Bart},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2007},
  pages     = {2293-2299},
  url       = {https://mlanthology.org/ijcai/2007/gomes2007ijcai-sampling/}
}