Random Problems

Random instances were generated using the extended model B as it is described by Bessiére et al. bmfl99. To summarize this generation method, a random non-binary CSP is defined by the following five input parameters:

n

- number of variables

d

- uniform domain size

k

- uniform arity of the constraints

p

- density ($\%$) percentage of the generated graph, i.e. the ratio between existing constraints and the number of possible sets of $k$ variables

q

- uniform looseness ($\%$) percentage of the constraints, i.e. the ratio between allowed tuples and the $d^k$ total tuples of a constraint

The constraints and the allowed tuples were generated following a uniform distribution. We made sure that the generated graphs were connected. In the following, a class of non-binary CSPs will be denoted by a tuple of the form $<n,d,k,p,q>$. We use a star ($*$) for the case where one of the parameters is varied. For example, the tuple $<50,20,3,10,*>$ stands for the class of problems with 50 variables, domain size 20, arity 3, graph density 10$\%$, and varying constraint looseness.