In common with many previous studies of the transition phenomenon, we use
random binary CSPs and graph coloring as example classes of search problems.
This section describes how the problems were generated and searched.
The constraint satisfaction problems used in most of our experimental results consist of 10 variables with three possible values for each one, and in some cases, we repeated experiments with problems of 20 variables. Problem constraints are specified by a number of binary nogoods, i.e., assignments to a pair of variables that are considered to be inconsistent. The search problem is then to find a consistent complete assignment, i.e., a value for each variable that does not include any of the inconsistent pairs.
We generated problems in a number of ways to fully sample the range of behaviors. In the first method (``generate-select'') we generate CSPs by randomly selecting the specified number of binary nogoods. To produce classes of problems with restrictions on their number of solutions, we determine the number of solutions of these randomly generated problems and retain only those satisfying these restrictions. For example, to produce a class of solvable problems, only those with a solution are included. Similarly, to produce a class of problems with a fixed number of solutions, only those problems with exactly the specified number of solutions are retained.
This random generation method gives a simple, uniform selection from the various problem classes. However, it can also be very inefficient in generating problems. For instance, with few nogoods, most randomly generated problems are solvable, hence requiring a large number of random trials to obtain even a few unsolvable cases.
To address this problem, we also used more efficient (``hill-climbing'') methods. Specifically, for generating solvable problems with many nogoods, starting with a randomly generated unsolvable problem, we removed constraints at random until the problem became solvable, then restored the number of constraints removed with constraints chosen randomly, but with the requirement that the problem not become unsolvable again.
For generating unsolvable problems with few nogoods, the hill-climbing method started with a randomly generated solvable problem, removed the constraint that constrained the problem the least (the one whose removal increased the number of solutions the least), and added a randomly chosen constraint that resulted in a problem with fewer solutions than the problem had before the constraint removal. If, having removed one constraint, no other constraint could decrease the number of solutions, the constraint that increased the number of solutions the least was chosen - a slightly backwards step. To speed this process up, we checked only one third of the possible constraints before giving up, choosing the one that increased the number of solutions the least, and starting another iteration.
Other methods for generating problems with specified requirements on the number of solutions have also been studied. One popular method for solvable problems is to randomly select an assignment to all of the variables (a pre-specified solution) and then, during the random selection of nogoods, avoid any that are inconsistent with this pre-specified solution. This tends to emphasize problems with many solutions and results in instances that are somewhat easier than uniform random selection. [3] have also used the approach of generating problems with specific attributes, for SAT problems, using the AIM generators [1].
We solved these problems using dynamic backtracking [10]
in most cases, using random variable and value ordering. For
comparison, we also did some searches with simple chronological
backtrack instead. The search cost is measured as the number of nodes
explored.
We also experimented with the 3-coloring problem. This constraint
satisfaction problem consists of a graph and the requirement to assign
each node one of three colors so that no pair of nodes linked by an
edge have the same color. Each edge in the graph defines some binary
nogoods for the problem, namely all pairs of assignments giving the same
color to the two nodes connected by the edge. Thus each edge in the graph
gives three binary nogoods. A convenient measure of the number of
constraints is 
, the connectivity or average degree of the
nodes in the graph. This is equal to twice the number of edges in the
graph divided by the number of nodes, because each edge is incident on
two nodes. For the 100-node graphs we studied, the number of binary
nogoods is given by 
.
In this case, we used a simple chronological backtrack search in combination with the Brelaz heuristic for variable and value ordering [13]. This heuristic assigns the most constrained nodes first (i.e., those with the most distinctly colored neighbors), breaking ties by choosing nodes with the most uncolored neighbors, and with any remaining ties broken randomly. The colors are considered in a fixed ordering for all of the nodes in the search. As a simple optimization, the search never changes the colors selected for the first two nodes. Any such changes would amount to unnecessarily repeating the search with a permutation of the colors for unsolvable cases. Search cost is measured by the number of nodes explored.
Previous: 1. Introduction
Next: 3. The Easy-Hard-Easy
Pattern
Return to Contents
Send comments to mammen@cs.umass.edu