Generating Random Solutions for Constraint Satisfaction Problems

The paper presents a method for generating solutions of a constraint satisfaction problem (CSP) uniformly at random. The main idea is to transform the constraint network into a belief network that expresses a uniform random distribution over its set of solutions and then use known sampling algorithms over belief networks. The motivation for this tasks comes from hardware verification. Random test program generation for hardware verification can be modeled and performed through CSP techniques, and is an application in which uniform random solution sampling is required.

Authors

• Rina Dechter and Kalev Kask University of California
• Irvine; Eyal Bin and Roy Emek IBM Research Laboratory in Haifa

Keywords

No keywords are indexed for this paper.