Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints
Carla Pedro Gomes, Ashish Sabharwal, Bart Selman · The MIT Press eBooks · 2007
We propose a new technique for sampling the solutions of combinatorial prob-lems in a near-uniform manner. We focus on problems specied as a Boolean for-mula, i.e., on SAT instances. Sampling for SAT problems has been shown to have interesting connections with probabilistic reasoning, making practical sampling algorithms for SAT highly desirable. The best current approaches are based on Markov Chain Monte Carlo methods, which have some practical limitations. Our approach exploits combinatorial properties of random parity (XOR) constraints to prune away solutions near-uniformly. The nal sample is identied amongst the remaining ones using a state-of-the-art SAT solver. The resulting sampling dis-tribution is provably arbitrarily close to uniform. Our experiments show that our technique achieves a signicantly better sampling quality than the best alternative. 1