Generating Random Solutions for Constraint Satisfaction Problems

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

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.