A Generator for Random Non-Binary Finite Constraint Satisfaction Problems
Hui Zhi Zou, Berthe Y. Choueiry, Amy M. Davis · Lincoln (University of Nebraska) · 2002
The paper describes an implementation of a generator of random instances of non-binary constraint satisfaction problems that meets a given set of specifications. This is a continuation of the work we started in [1]. 1 Description The program is designed to generate random instances of Constraint Satisfaction Problems (CSPs) that meet a set of specified parameters, such as the number of variables, domain size, constraint density, tightness. At the same time, it can generate any combination of binary, ternary, and/or quaternary constraints specifies as percentage of the total number of constraints in the problem. 2 Assumptions To realize this program, we make the following assumptions: 1. All variables have the same domains. 2. Any particular group of variables has only one constraint of a given arity. 3. All constraints have the same tightness. 4. All variables are equally likely to be connected by a constraint. 5. We guarantee that the resulting CSP is connected. 3 Parameters The input parameters are the following: .