- Technical Program
- Workshops & Tutorials
- At a glance
- Doctoral Consortium
- Opening & Reception
- Best Papers from Sister Conferences Track
- IJCAI Video Track
- Trading Agent Competion (TAC)
- IJCAI-11 Awards
- Funding Opportunities for International Research Collaborations
- General Game Playing Competition
- Banquet
- Ramon Llull Session
- Industry Day
- Closing Event
- List of Accepted Papers
- Poster Boards

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

Stefano Ermon, Carla Gomes, Bart Selman

Consider a combinatorial state space S, such as the set of all possible truth assignments of 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 very general and has many applications. For instance, if we consider of 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, MAX-SAT 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 the flat histogram idea and on a random walk component. 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.