---
title: "A Flat Histogram Method for Computing the Density of States of Combinatorial Problems"
authors:
  - "Stefano Ermon"
  - "Carla P. Gomes"
  - "Bart Selman"
doi: "10.5591/978-1-57735-516-8/IJCAI11-434"
url: "https://ijcai.org/proceedings/2011/434"
pdf: "https://ijcai.org/proceedings/2011/0434.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "2608-2612"
track: ""
keywords:
---

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

Stefano Ermon, Carla P. Gomes, Bart Selman

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 2608-2612. DOI: [10.5591/978-1-57735-516-8/IJCAI11-434](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.