Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems

y

TAKING ADVANTAGE OF STABLE SETS OF VARIABLES IN CONSTRAINT SATISFACTION PROBLEMS

Eugene C. Freuder and Michael J. Quinn *

Department of Computer Science, University of New Hampshire, Durham, NH 03824

ABSTRACT

Binary constraint satisfaction problems involve finding values for variables su bject to constraints between pairs of variables. Algorithms that take advantage of the structure of constraint connections can be more efficient than simple backtrack search. Some pairs of variables may have no direct constraint between them, even if they are linked indirectly through a chain of constraints involving other variables. A set of variables with no direct constraint between any pair of them forms a stable set in a constraint graph representation of a problem. We describe an algorithm designed to take advantage of stable sets of variables, and give experimental evidence that it can outperform not only simple backtracking, but also forward checking, one of the best variants of backtrack search. Potential applications to parallel processing are noted . Some light is shed on the question of how and when a constraint sat isfaction problem can be advantageously divided into subproblems.

I DIRECT INDEPENDENCE OF VARIABLES

Constraint satisfaction problems involve finding values for vari­ ables subject to constraints, or relations among the variables. Often these constraints are restrict~d to being binary relations between two variables; we shall consider binary constraints here. Standard back­ trac k search can be used to 'olve such problems. In generat the upper bound on the complexity of the search is exponential in the number of variables.

* The authors' names appear in alphabetical order.

In this paper we propose taking advantage of the "relative in­ dependence" of variables to ameliorate the search complexity. We term two variables directly independent if there is no direct constraint between them, even if they may be indirectly related by a chain of constraints passing through intermediate variables.

The basic insight is illustrated by the example in Figure 1. The problern involves three variables, each with three possible values, and a constraint graph (Figure 1a, 1b). Links in the graph represent con­ straints; nodes represent variables. Note that there is no direct con­ straint between variables y and z. U we approach the problern with a Straightforward backtracking algorithm, we might have to examine almost 3 x {3 x 3) or 27 possible triples of values before hitting upon a solution in the rightmost branch of the search tree. More than 27 tests on pairs of values would be performed (Figure 1c).

Now Iet us take into account the relative independence of variables y and z. Having chosen a value for x, we can go ahead and choose a value for y and a value for z independently. There will be at most 6 values to consider {3 for each) before we succeed or fail. If we fail , we repeat the process for the next x value. At most we will perform 3 x {3 + 3) or 18 tests on pairs of values (Figure ld) .

In generat we can partition constraint graphs into sets of "mu­ tually independent" variables, where there is no direct constraint be­ tween any pair of variables in the set. Such a set is called a stable set in graph theory. Consider the constraint graph shown in Figure 2, for the problern of labeling the cube. The scene labeling problern !Waltz, 1975J provides an application domain here, but those unfamiliar with it can regard the cube as an abstract constraint graph .. The graph in Figure 2b is simply a redrawing of the constraint graph in Figure 2a. Observe that the variables F and C are not joined by a constraint , nor are B and D, nor A and E. There are no edges between variables at the same Ievel in Figure 2b. Once a value has been chosen for G, the values for F and C may be chosen mutually independently, then values for B and D, and so on. (Figure 2b is a generalized form of an "ordered constraint graph" !Freuder, 1982J.)

Many interesting improvements on basic backtracking have been made IHaralick and Elliott , 1980; Gaschnig, 1978J. Generally these improvements operate at a "microlevel," involving the relationships between individual values for variables, e.g., value a for variable x is inconsistent with value b for variable y. Our concerns are at a "ma.crolevel," involving the relationships between the variables them­ selves, e.g., there is no constraint between variables x and y. A more detailed experimental comparison with one of the best of the backtrack variations is made later.

li PSEUDO-TREE SEARCH ALGORITHM

Given a constraint graph partitioned into stable 'sets, we would like to t ake advantage of direct independence not only on one maximal st ableset (or an approximation thereof) , but on all the stable sets. For example, we would Iike to use the stable sets identified in Figure 2 as "Ievels" in a generalized backtrack algorithm that employed the basic "additive" insight of Section I at each Ievel.

This can be done, up to a point, in a Straightforward way. Pro­ ceeding down through the Ievels, each variable at a given Ievel can be considered independently. However, a problern arises in backtracking. lf two variables at one Ievel have a constraint path down to a single variable at a lower Ievel (as in Figure 2b) , all combinations of values for t he two higher Ievel variables may need to be tried before finding one compat ible with the lower Ievel variable. Thus, we again have a "multiplicative" rather than an "additive" effect.

Definition: A pseudo-tree is a rooted tree T = (V, E) augmented with zero or more additional edges E' such that all edges between some vertex v and vertices closer to the root lie a long the path in T from v to the root. The Ievel of a variable in a pseudo-tree is its Ievel in t he underlying rooted tree.

A pseudo-t ree structured constraint graph supports an algorit hm that avoids the "multiplicative backtracking" problern cited above. l t also makes it easy to determine what. variables need to be mod­ ified during backtracking. Thirdly, the pseudo-tree property makes t he constraint satisfaction problem more amenable to solut ion on a multiprocessor , because a processor could try to assign values to a variable and. all its descendents without having t o communicate wit h other processors [Freuder and Quinn , 1985).

Pseudo-Tree Search Algorithm

m- number of Ievels in pseudo-tree size(i )- number of variables at Ievel i a(i, j )- jth variable at Ievel i { 1, 2, ... , choices (a(i, j )) }- potential values of a(i, j ) value(a(i, j))- current value of a(i, j) parent(a(i , J))- index of parent of a(i , j) at Ievel i - 1 for i := 1 to m do for J := 1 to size(i ) do value (a(i, j )) := 1 (* lnitialize allvariables *) endfor endfor ; i := 1; (* i is current search Ievel *) while (1 :,; i ) and (i :,; m) do ( · Examine Ievel i ·) . j := 1; repeat if value(a(i, j )) violates a constraint with an ancestor then while value(a(i,j )) violates a constraint do if value(a(i , j )) = choices(a(i , j )) then (* No more a lternatives for a(i, J )- must backtrack *) j := parent(a(i ,J)); i := i - 1 if i = 0 then exit outermost w hile loop endif endif; (* Former value Ieads to constraint conßict - try another · ) value(a(i, j )) := value(a(i , j )) + 1 endwhile; set value of all descendents of a(i , j ) to 1 end if; · j := j + 1 (* Try next variable at Ievel i * ) unt il j > size(i ); (* All constraints satisfied through Ievel i - deepen search *) i := i + 1 endwhile; if i > m then (* Solut ion found- it is stored in array value *) eise (* No solu t ion *) endif.

The following Iemma proves that the pseudo-tree search a lgori thm has a complexity· bound exponential in the number of Ievels "in the pseudo-tree, rather than in the number of variables in the prob lern. In the next sect ion we present an algorithm for transforming an arbit rary const raint satisfaction problern into an equivalent "met aproblem" with a pseudo-tree constraint graph structure.

Lemma: Given a pseudo-tree T and k variables at Ievel m in T , each variable capable of taking on b values, the search algori thm back­ tracks at most bk t imes to Ievel m before backtracking to Ievel m - 1.

Proof: The first time the search algorithm reaches Ievel m, the value of every variable at that Ievel is initialized as low a.s possible. The search algori t hm backtracks from Ievel m + 1 in T when there exists at t hat Ievel a variable u t hat cannot be given a value that does not violate constrain ts with t he values of ancestor variables in T. By the pseudo-tree property, all of the variables constraining v lie along a simple path from v to the root ofT. In order to try all combinations of values that might Iead to an allowable value of u, only variables along this path need to have their values changed . Hence every time the search backtracks to Ievel m , exactly one of the variables w at Ievel m must have its value modified. The va lue of w cannot be decremented: all lower values were previously held by w and led to a backt racking lower in the tree. Because it is only necessary to reset the value of w when one of its ancestors has its value incremented , the value of no variable at Ievel m willlower un t il the search backtracks from Ievel m. Since there are k variables, each with b possible va lues, t he maximum number of values variables at Ievel m can take on before one vari able has no more possible values is bk.

Theorem: Given a pseudo-tree T with m Ievels, each Ievel i con­ t aining k; variables capable of taking on b, values, the worst-case time complexity of our algorit.hm is 8(Di~ 1 b, k;).

Corollary: Given a pseudo-t ree T , our algori thm can fi nd one as­ signment of values to variables that satisfi es the const.raints, if one exists, but it cannot be used to find all solutions t hat satisfy the con­ straints.

III DERIVING PSEUDO-TREE METAPROBLEMS

A constrain t graph can be subdivided into subproblems, where each subproblem involves satisfying a subset of the original variables. The problem of satisfying all the subproblems simultaneously may then be regarded as a metaprobJem , with the subproblems as metavariabJes.

It has long been recognized that part it ioning a constraint sat isfac­ tion problern in to subproblems may simplify t he problem . However , little guidance is available as to how and when to subdivide problems. One criterion for considering a probiem subdivision is t he felic­ ity of the structure of t he resul t ing metaproblem. For example, if the metaproblem has a tree structured constraint graph on the metavari­ ables, then it can be solved in time linear in the number of metavari­ ables [Mackworth and Freuder, to appear). Here we present a method for producing a met aproblem where t he met avariables are organized in to stable sets forming Ievels in a pseudo-tree constraint structure. Recall that the previous section presented an a lgorithm for pseudo­ t ree-structured problems, wi th a complexity bound exponential in the

number of pseudo-tree Ievels.

The original problern is partitioned into a met aproblern as follows:

1. Find a cut set in the constraint graph ; i.e., a set of vert ices whose removal divides t he graph into two or more unconnected subgraphs. The cut. set S corresponds to [S [ variables in the met aproblem; t.hese metavariables will form t he first [S [ Ievels of the pseudo-tree. The unconnected subgraphs temporarily become metavariables and are children of the variable in S deepest in the "tree ."
2. Apply thi s process recursively to each of the children, terminat ing when the subgraph being examined cannot be split further.

The algorithm will not necessarily produce an "opt imal" pseudo­ tree. We would like to be cert.a in of efficiently t ransforming a given constraint graph into a pseudo-tree structure which takesopt imal (or nearly optimal) advantage of direct independence. This remains an area for furt.her work .

IV EXPERIMENTAL RESULTS

To experimentally verify the efficiency of this algorithm, we have used it to try to color graphs with three colors. The performance of our algorithm is contrasted with two others. The first algori thm performs simple backtracking, where t he order in which the variables are searched is randomly chosen. The second algorit.hm uses forward checking ! Raraliek and Elliott , 1980), which Rara liek and Elliot showed to be superior to several other variants of backtracking under certain experimental conditions. The order in which variables are considered corresponds to a level-by-level t raversal of the pseudo-t ree.

The form of the test graphs is shown in Figure 3. Notice that we have created constraint graphs that have the pseudo-tree property, which avoids the previously-mentioned problern of efficiently trans­ forming constraint graphs into pseudo-trees. Wehave tested the three algorithms on a I arge number of graphs. Foreach problern size ranging from 4 to 36 variables, we have generated 100 random pseudo-tr~es. Wehaverun the three search algorithms on all 900 graphs, measuring the number of constraint checks made by each algorithm. Each result has been put into one of two categories, depending upon whether the graph is three-colorable or not. This is because unsuccessful searches require many more constraint checks on average. Figure 4 displays the mean number of constraint checks performed by the three algorithms for successful and unsuccessful searches of the various graphs. Not only does our algorithm outperform standard backtracking, it also performs substantially fewer constraint checks than the forward checking algo­ rithm on both colorable and uncolorable graphs. (We have also com­ puted the median number of constraint checks performed by the three algorithms. Our algorithm outperforms standard backtracking and forw ard checking on unsuccessful searches and standard backtracking on successfu) searches. However, the median number of constraint checks performed by forward checking on successful searches is a few percent. lower than the number performed by our algorithm.)

Certainly our search algorithm will not outperform other algo­ rithms, such as forward checking, in all situations. The constraints must fit a certain pattern in order to benefit from our exploitation of direct independence. For example, if our met.hodology were applied to the eight-queens problern (placing eight queens on a chess board so that. no queen can attack another) , the pseudo-tree would have eight Ievels, and the search algorithm would degenerate into standard backt.racking.

In fact , much of the experimental work on backtrack search has been clone in the context of the eight-queens problem. This is actually a very specialized type of problem: the constraint graph is complete, all constraints are the same, and all variables have the same domain. Direct independence in a constraint graph is in a sense the opposite of completeness; it involves subsets of variables, which, far from forming complete subgraphs, form stable sets, where no variable is connected to any ot.her.

V CONCLUSIONS

Wehave presented an algorithm tailored to solve constraint satis­ faction problems on constraint graphs that have the pseudo-tree prop­ erty. We have also described an algorithm for turning any constraint graph into a constraint· graph with the pseudo-tree property. Experi­ mental evidence indicates there exist constraint graphs for which our algorithm outperforms not only standard backtracking, but also for­ ward checking.

ACKNOWLEDGMENTS

This paper is based in part upon work supported by the National Science Foundation under Grant MCS 8003307.