Uniform Solution Sampling Using a Constraint Solver As an Oracle

Stefano Ermon, Carla P. Gomes, Bart Selman
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:253-262, 2012.

Abstract

We consider the problem of sampling from solutions defined by a set of hard constraints on a combinatorial space. We propose a new sampling technique that, while enforcing a uniform exploration of the search space, leverages the reasoning power of a systematic constraint solver in a black-box scheme. We present a series of challenging domains, such as energy barriers and highly asymmetric spaces, that reveal the difficulties introduced by hard constraints. We demonstrate that standard approaches such as Simulated Annealing and Gibbs Sampling are greatly affected, while our new technique can overcome many of these difficulties. Finally, we show that our sampling scheme naturally defines a new approximate model counting technique, which we empirically show to be very accurate on a range of benchmark problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-ermon12a, title = {Uniform Solution Sampling Using a Constraint Solver As an Oracle}, author = {Ermon, Stefano and Gomes, Carla P. and Selman, Bart}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {253--262}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/ermon12a/ermon12a.pdf}, url = {https://proceedings.mlr.press/r10/ermon12a.html}, abstract = {We consider the problem of sampling from solutions defined by a set of hard constraints on a combinatorial space. We propose a new sampling technique that, while enforcing a uniform exploration of the search space, leverages the reasoning power of a systematic constraint solver in a black-box scheme. We present a series of challenging domains, such as energy barriers and highly asymmetric spaces, that reveal the difficulties introduced by hard constraints. We demonstrate that standard approaches such as Simulated Annealing and Gibbs Sampling are greatly affected, while our new technique can overcome many of these difficulties. Finally, we show that our sampling scheme naturally defines a new approximate model counting technique, which we empirically show to be very accurate on a range of benchmark problems.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Uniform Solution Sampling Using a Constraint Solver As an Oracle %A Stefano Ermon %A Carla P. Gomes %A Bart Selman %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-ermon12a %I PMLR %P 253--262 %U https://proceedings.mlr.press/r10/ermon12a.html %V R10 %X We consider the problem of sampling from solutions defined by a set of hard constraints on a combinatorial space. We propose a new sampling technique that, while enforcing a uniform exploration of the search space, leverages the reasoning power of a systematic constraint solver in a black-box scheme. We present a series of challenging domains, such as energy barriers and highly asymmetric spaces, that reveal the difficulties introduced by hard constraints. We demonstrate that standard approaches such as Simulated Annealing and Gibbs Sampling are greatly affected, while our new technique can overcome many of these difficulties. Finally, we show that our sampling scheme naturally defines a new approximate model counting technique, which we empirically show to be very accurate on a range of benchmark problems. %Z Reissued by PMLR on 04 October 2026.
APA
Ermon, S., Gomes, C.P. & Selman, B.. (2012). Uniform Solution Sampling Using a Constraint Solver As an Oracle. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:253-262 Available from https://proceedings.mlr.press/r10/ermon12a.html. Reissued by PMLR on 04 October 2026.

Related Material