A Flat Histogram Method for Computing the Density of States of Combinatorial Problems

Ermon, Stefano; Gomes, Carla P.; Selman, Bart

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

A Flat Histogram Method for Computing the Density of States of Combinatorial Problems

Stefano Ermon, Carla P. Gomes, Bart Selman

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2608-2612.

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

Abstract

Consider a combinatorial state space S, such as the set of all truth assignments to N Boolean variables. Given a partition of S, we consider the problem of estimating the size of all the subsets in which S is divided. This problem, also known as computing the density of states, is quite general and has many applications. For instance, if we consider a Boolean formula in CNF and we partition according to the number of violated constraints, computing the density of states is a generalization of both SAT, MAXSAT and model counting. We propose a novel Markov Chain Monte Carlo algorithm to compute the density of states of Boolean formulas that is based on a flat histogram approach. Our method represents a new approach to a variety of inference, learning, and counting problems. We demonstrate its practical effectiveness by showing that the method converges quickly to an accurate solution on a range of synthetic and real-world instances.

Stefano Ermon, Carla P. Gomes, and Bart Selman. 2011. A Flat Histogram Method for Computing the Density of States of Combinatorial Problems. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2608–2612. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-434

@inproceedings{ijcai2011p434,
  title     = {A Flat Histogram Method for Computing the Density of States of Combinatorial Problems},
  author    = {Ermon, Stefano and Gomes, Carla P. and Selman, Bart},
  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     = {2608--2612},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-434},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-434},
}

TY  - CPAPER
TI  - A Flat Histogram Method for Computing the Density of States of Combinatorial Problems
AU  - Ermon, Stefano
AU  - Gomes, Carla P.
AU  - Selman, Bart
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  - 2608
EP  - 2612
DO  - 10.5591/978-1-57735-516-8/IJCAI11-434
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-434
ER  -