Approximate Inference for Clusters in Solution Spaces

This work proposes new approximate (and exact) inference methods for reasoning about an important and hard-to-compute property of the solution space of combinatorial problems, namely clusters of solutions. We introduce an approximate method that first reformulates the constraint satisfaction problem (CSP) as a "factor graph" over an extended set of variable domains, approximates the number of clusters using an exponential size expression defined over this factor graph, and then estimates the value of this expression using message passing techniques, specifically an extension of the belief propagation (BP) algorithm. We provide formal exactness results as well as an empirical evaluation attesting to the accuracy of our method in counting the number of solution clusters.