GSAT and Local Consistency

1 Introduction

Local search algorithms like min-conflicts [Minton et al., 1990] and GSAT [Selman et al., 1992] have been success­ fully applied to different classes of constraint satisfaction problems like SAT, graph coloring, binary CSP~ and scheduling. The popularity of local search algonthms can be attributed to their efficiency - they can outper­ form complete systematic search methods like backtrack­ ing and backjumping on large classes of problems. The question that arises is whether local search methods are always better, or at least not worse, than complete sys­ tematic search methods. This question is somewhat am­ biguous since there is no one single version of GSAT - most of them employ clever heuristics that signifi­ cantly improve their performance over the basic version of GSAT reported in [Selman et al., 1992]. Moreover, several problems that once seemed very hard have been

·This work was partially supported by NSF grant IRI9157636, by the Electrical Power Research Institute (EPRI), and by grants from Toshiba of America, Xerox Northrop and Rockwell.

Rina Dechter

Computer Science Department University of California at Irvine Irvine, CA 92717 USA

successfully solved once certain heuristics, like clause weighting and random walk, were added to GSAT.

In this paper we will investigate whether or not GSAT can be improved by applying preprocessing. Preprocess­ ing algorithms are run on the problem in advance, before the search algorithm is tried, and change the problem representation into a different, but equivalent one. Pre­ processing algorithms include a variety of consistency­ enforcement algorithms. These algorithms make the problem more explicit by adding new constraints that are induced by the existing co.nstraints. Enforcing local con­ sistency can improve the performance of complete sys­ tematic search methods like backtracking and backjump­ ing by eliminating dead ends, thus red~cing the sear~h space. We will apply the idea of enforcmg local consis­ tency to GSAT with the hope that its performance can also be improved by making the problem more explicit. In particular, we will focus on different forms of partial path consistency since full path consistency is not cost effective for large problem instances.

We will focus on two different classes of problems- ran­ dom uniform problems that do not have any structure and random structured problems. As we will show, local consistency has a very different effect on the performance of GSAT on these two classes of problems. On uniform random problems, enforcing local consistency can help GSAT solve more problems but the overhead associated with enforcing local consistency and the added complex­ ity of induced constraints eliminates any net gain. How­ ever on a class of structured cluster problems, local consistency dramatically improved the performance of GSAT.

In a recent paper [Konolige, 1994] it was shown that there are certain classes of structured problems that are very hard for GSAT, even if the best currently known heuristics like clause weighting and random walk are used, while being very easy for the Davis-Putnam pro­ cedure. In this paper we will examine a similar class of structured 3SAT problems. These problems have a clus­ ter structure - they contain clusters of variables each of which is a small group of variables tightly linked with constraints (3-SAT clauses). Clusters themselves are linked together by a different set of constraints (3-SAT clauses). It turns out that these kinds of hierarchical problems can be extremely hard for GSAT using the best currently known heuristics. But surprisingly, these problems will become trivial for GSAT once a certain amount of local consistency is enforced, in this case a restricted form of Bound-3 resolution. The effect of en­ forcing this kind of local consistency is that it makes constraints more explicit by adding new induced con­ straints. This will change the GSAT search space by eliminating many near solutions 1 so that they will be­ come assignments whose cost is high.

2 GSAT

Local search algorithms like GSAT work by first choosing an initial assignment and then incrementally improving it by flipping the value of a variable so that the new value leads to the largest increase in the number of satisfied constraints. This is done until all constraints are satis­ fied , or a predetermined number of flips (MAX_FLIPS) is reached, or GSAT reaches a local minimum.

The following is a standard GSAT procedure:

Procedure GSAT (CSP problem P, MAX_TRIES, MAX_FLIPS)

for i=1 to MAX_TRIES

let A be a random initial assignment

for j=1 to MAX_FLIPS

if A satisfies P, return true

else let F be the set of variable-value pairs that, when flipped to, give a maximum increase in the number of satisfied constraints; pick one f E F and let new A be current A with f flipped

end

end return false end

This algorithm is almost never used in practice as it is here because its performance can be improved signif­ icantly by adding a number of heuristics. Our version of GSAT uses several heuristics that include, we believe, the best known heuristics today.

The basic GSAT is non-deterministic because it does not specify how to break ties between two or more vari­ ables having an equally good flip, or between two or more values that would give the same increase. [Gent and Walsh, 1993] suggest using historic information in­ stead of breaking ties randomly. They propose that in the event of a tie, a variable that was flipped the longest ago be chosen.

We also use clause weighting as proposed by the Breakout method of P. Morris [Morris, 1993] and in a different form in [Selman and Kautz, 1993]. This method proposes a method of escaping local minimums by reweighting constraints. In addition, we use a version of random walk called random noise strategy in [Sel­ man et al., 1992]. This method suggests picking, with probability p, a variable that appears in an unsatisfied constraint and flipping its value. Unlike [Selman et al., 1992], we flip not one, but three variables at a time and the probability pis not 50-60%, but 10-15%. This gives a little improvement over the original method because if only one variable is flipped, most of the time GSAT will flip it right back.

1 Near solutions are assignments that have a cost of almost zero.

The third heuristic we use is similar to the one pro­ posed in [Yugami et al., 1994]. Their method proposes a way of escaping local minimums by using value propaga­ tion over unsatisfied constraints. We pick an unsatisfied constraint and check to see if it contains any variables whose value has not yet been flipped. If there is at least one, we will flip one of them so that the constraint be­ comes satisfied. There are two differences in what we do - [Yugami et al., 1994] computes a closure under value propagation, whereas we do only a fixed number of steps. Second, in [Yugami et al., 1994] this is done every time a local minimum is reached. We do it only at the end of every try as a way of generating a new initial assignment for the next try.

Last, there is always the problem of choosing MAX_TRIES and MAX_FLIPS. We solve this problem by using a heuristic that determines the length of every try (ie. MAX_FLIPS) automatically during every try [Hampson, 1993] . The idea is that we search as long as we are making progress, and if we haven't made progress for a while we give up and start a new try. Progress is measured as finding an assignment that satisfies more constraints than satisfied by any other assignment found by GSAT during that particular try. Every time we find such an assignment, we give GSAT time equal to the amount of time it has spent up until that point from the beginning of the try. If during this time no better assignment was found, we give up and start a new try. Using this strategy, we need to give only one parameter, MaxFlips, that bounds the total maximum number of flips that GSAT will spend on a problem.

3 Problem Format

The first class of 3SAT problems we experimented with is a set of cluster structures. These problems are char­ acterized by the following parameters:

1. N - the number of variables per cluster.
2. C- the number of clauses per cluster.
3. eN - the number of clusters.
4. eC - the number of clauses between clusters.

Every cluster structure is generated by first generating eN clusters (each N variables and C clauses) and then generating cC clauses such that all 3 variables in a clause come from different clusters.

We also used binary constraint satisfaction problems such that all variables had the same domain of size K of natural numbers {1, ... , K} . All binary CSP problems are characterized by the following parameters:

1. N - the number of variables.
2. K - the number of values.
3. C - the number of constraints. For binary constraints Cmax = N · (N- 1)/2.
4. T- the tightness of the constraint, as a fraction of the maximum K 2 pairs of values that are nogoods.

Every binary CSP problem is generated by first uni­ formly randomly choosing C pairs of variables and then creating a constraint for every pair. To create a con­ straint, we randomly pick T x K 2 tuples and mark them as pairs of values that are allowed.

When evaluating the performance of an algorithm, it is always important to know how many of the problems that were tried were actually solvable. This introduces an additional problem for GSAT since it is an incom­ plete algorithm. Normally in this situation, every prob­ lem is first solved using the Davis-Putnam procedure or any other complete algorithm. Unfortunately, this al­ lows us to solve only small problems. Real life problems are likely to be large and intractable for any complete al­ gorithm known today. We can get around this problem if we can generate problems for which we know in ad­ vance that they are solvable. The straightforward way of getting solvable 3SAT formulas is to first generate a solution and then generate random clauses and keep only those that are satisfied by the solution (in other words, at least one literal in the clause matches the so­ lution). Unfortunately, these kind of problems are very easy. However, it turns out that if we throw away not only those clauses that have 0 literals satisfied by the so­ lution, but also those that have exactly 2 literals satisfied by the solution we get random 3SAT problems that are on the average at least as hard, for GSAT, as the class of all solvable problems. All 3SAT cluster structures tested in this paper were generated this way.

Another property of solvable 3SAT formulas gener­ ated this way is that when the formulas are uniformly randomly generated, the hardest problems for GSAT are in the area where the ratio of the number of variables to the number of clauses is between 4.5 and 5. When this ratio is smaller or larger, problems are easy for GSAT. For example, when the ratio is 8, problems have only 1 solution 2 and on the average, finding this only solution is much easier for GSAT than solving a problem from the 4.5 - 5 range.

2 We know there is only one solution because when we com­ pute the closure under Bound-3 resolution we almost always

4 Random Cluster Structures

On the class of cluster problems described in the previ­ ous section GSAT performs very poorly. In Table 1. we have the results of experiments with cluster structures of eN = 50 clusters, cC = 200 clauses between clusters, N = 5 variables per cluster and C = 30 - 40 clauses per cluster. Each cluster by itself is very easy for GSAT because it is strongly over-constrained (the ratio of the number of clauses over the number of variables varies from 6 to 8) and as a result each cluster has only very few solutions. But taken together they appear extremely difficult for GSAT. For example, when the number of clauses per cluster grows from 30 to 37 the number of problems GSAT is able to solve drops from 100 to 41, and it takes on the average 252,000 flips to find a solu­ tion when it can find one (the upper bound M axF lips is 512K) . When we increase the number of clauses per cluster to 40, GSAT fails to solve any problems (remem­ ber that all problems are solvable). For comparison, we have also included the running time of the Davis-Putnam procedure on the same problems.

This is surprising since 250 variable uniform random 3SAT formulas are fairly easy for this GSAT program. Our hypothesis is that this phenomena can be attributed to the structure of the problem. When the number of clauses per cluster increases from 30 to 40, the num­ ber of solutions each cluster has, when taken separately, decreases from a few to one. But the number of near solutions 3 remains large. When we start GSAT on an initial assignment, it always quickly converges to an as­ signment that is a near solution. The hardest part for any GSAT algorithm is to improve a near solution so that it becomes a real solution. On the cluster prob­ lems, GSAT quickly finds an assignment that for many clusters is a near solution. But it seems to be unable to improve this assignment . In order to improve it many changes in different clusters need to be made. But the structure of the problem - tight clusters with loose con­ straints between them - does not provide good guidance for GSAT.

However, we can enforce local consistency that will change the structure of the problem by adding new, in­ duced constraints. We ran GSAT on the same problems after a preprocessing algorithm RBR-3 was run on them. RBR-3 computes a restricted form of Bound-3 resolution [Dechter and Rish, 1994] by resolving only pairs of origi­ nal clauses and keeps only those resolvents that have no more that 3 literals. The results of these experiments are

get a total of Cma:r = 7 · ( ~ ) clauses, which is the maxin Table 1. We see that after RBR-3 was run, problems became almost trivial. GSAT can solve all problems and on the average it needs only 115-190 flips . Almost all of the time was used by RBR-3.

imum number of clauses a solvable 3SAT formula can have. Also, when we have Cma:r clauses, the formula has only one solution. Finally, notice that new clauses added by Bound-3 resolution do not remove any solutions of the original formula.

3 A near solution is an assignment that satisfies almost all clauses, and therefore, for which the value of the cost function is almost zero.

When we look at where the new clauses are added we see that almost all of them are local clauses, namely all three literals are from the same cluster. In fact, the total number of clauses per cluster roughly doubles and is close to the maximum possible number of clauses Cmax = 7 ·

( ~ ) that a solvable 3SAT problem can have. This

has the effect of eliminating many near solutions. Many assignments that previously satisfied all, except very few, clauses violate many of the new induced clauses.

5 Random Uniform Problems

What Bound-3 resolution did to cluster structures was that it added new induced constraints that in effect changed the search space by eliminating many near so­ lutions. It would be natural to ask what would be the effect of local consistency enforcement on problems that do not have any special structure to begin with. Can they benefit the same way cluster structures did?

In this section we will focus on uniform random prob­ lems - the constraint graph of which does not have any special structure. We ran a series of experiments with both binary CSP problems and 3SAT formulas . Given a random problem, first we ran a local consistency enforce­ ment algorithm and then ran GSAT. On 3SAT formulas, the local consistency algorithm computes a closure under Bound-3 resolution. On binary CSPs, the local consis­ tency algorithm computes partial path consistency. We now take (in section 5.1) a small detour to discuss dif­ ferent versions of path-consistency algorithms.

5.1 Partial Path Consistency

A problem is path consistent (or 3-consistent) iff any in­ stantiation of any two variables that is locally consistent can be extended to a consistent assignment of any third variable [Montanari, 1974) . Enforcing path consistency makes the problem more explicit: constraints that are induced by other constraints are added to the problem and thus become explicit.

It was shown that path consistency can potentially im­ prove the performance of any backtracking search algo­ rithm [Mackworth, 1977), since it frequently eliminates all dead ends from the search space [Dechter and Meiri, 1994). It would be interesting to know if path consis­ tency will also improve any local search algorithm like GSAT.

Unfortunately the complexity of enforcing path con­ sistency is 0(n 3 k 3 ) which is too large for big problems. It was shown in [Dechter and Meiri, 1994) that for many problems the overhead of path consistency is not cost ef­ fective. Therefore instead of computing path consistency exactly we will approximate it by using a restricted form of path consistency called partial path consistency.

The idea is the following. We want partial path con­ sistency (PPC) to be as close to path consistency (PC) as possible. This means that whenever PC removes a tuple from a constraint, we would like PPC to do the same. In the extreme case, all tuples will be removed from the constraint and it becomes empty, which means that the problem is inconsistent. In the following exper­ iments we use that as a criteria to measure the quality of our PPC algorithm - whenever PC generates an empty constraint, we want PPC to also generate an empty con­ straint.

The amount of changes made by path consistency de­ pends on the amount of local consistency present in the problem in the beginning [van Beek, 1994), [van Beek and Dechter, 1994). Intuitively, the tighter the constraints and the denser the constraint graph, the more changes PC will make. It turns out that partial path consistency based on the following heuristic is almost as good as full path consistency - we choose a subset of the variables that have the highest degree and are tightly grouped to­ gether, and perform path consistency on the subproblem induced by these variables:

• (a) 100 variables, 8 values, 32/64 tightness
• (b) 100 variables, 8 values, 16/64 tightness

Figure 2: Full and Partial Path Consistency.

Procedure PPC (CSP problem P, number of variables chosen m, locality parameter C)

for i=1 ton

a; = degree of variable X;

end

let S be the set of variables and let S' = 0

for i=1 tom

let x be the variable in S with the largest a;

let S = S- x and let S' = S' U x

for all neighbors Xj of x in S

ai = ai + C

end

end

do path consistency on S'

end

where C is a "locality" parameter that determines the order in which variables are chosen. If C = 0 then it would result in a MaxDegree ordering; if C = n, then it would result in a MaxCardinality ordering ([Tarjan and Yannakakis, 1984]). Our experiments show that we should set C equal to the average degree of the variable

• (a) 100 variables, 8 values, 32/64 tightness
• (b) 100 variables, 8 values, 16/64 tightness

Figure 3: Full and Partial Path Consistency.

in the constraint graph. Parameter m is the number of variables chosen. Clearly, the larger m the closer par­ tial path consistency is to full path consistency, but the longer it takes to compute it. We used m = 40 which resulted in a partial path consistency algorithm that was close enough to path consistency, but took significantly less time on large problems.

We ran a number of experiments comparing PPC to PC. In Figures 2 and 3 we have the results of running both full and partial path consistency on 300 randomly generated problems with 100 variables and 8 values; and the tightness of 32/64 and 16/64. On the left side we have the running time per problem and on the right side we have the percentage of problems that were solvable or inconsistent, as a function of the density of the constraint graph (-c-100%). Cma.r

For the 32/64 tightness problems the hardest area (50% solvability) is when problems have about 250 (5% of the maximum possible) constraints and for the 16/64 tightness problems, the hardest area is when problems have 655 (14% of the maximum possible) constraints. As we can see, the effectiveness of path consistency depends on the tightness of the constraints. For 32/64 problems, both full and partial path consistency discover almost all inconsistent problems. For 16/64 problems, full path consistency is not able to discover inconsistent problems in the 50% area and will become effective only when the density of the constraint graph grows. We also see that partial path consistency is only slightly less effective than full path consistency, especially for problems with tight constraints.

We also tested arc consistency and found that while it was very fast, it very seldom changed the problem, ex­ cept for problems that were very overconstrained. This shows that although arc consistency is computationally attractive, having the worst case complexity of O(n 2 k 2 ), it is not nearly as powerful as path consistency, and will be useful only when constraints are very tight.

5.2 Local Consistency on Random Uniform Problems

In Table 2. we have the results of running GSAT on two sets of binary CSP problems, one with N = 100 vari­ ables, J{ = 8 values and tightness T = 32/64 (sparse constraint graphs) and the other with N = 30 variables, K = 64 values and T = 2048/4096 tightness 4 (dense con­ straint graphs). We ran two experiments on the same set of problems, first with just GSAT and then partial path consistency (PPC) followed by GSAT. For comparison we have included the average running time per problem of a backjumping algorithm with dynamic variable or­ dering of [Frost and Dechter, 1994].

As we can see, enforcing partial path consistency does help GSAT solve slightly more problems given the same upper bound MaxFlips. But if we include time in our consideration we see that this strategy is not very useful since the total time it takes to solve a problem gets much worse. There are two reasons for this. First, enforc­ ing (partial) path consistency is computationally expen­ sive, although the complexity of partial path consistency grows very slowly. Second, and more importantly, if the constraint graph was not complete, it will be complete after path consistency (or very close in case of partial path consistency) . This will add additional complexity to the GSAT search algorithm since it has to consider additional constraints at every step. Notice that for clus­ ter structures adding constraints was cost-effective while here it is not.

4 This tightness was chosen because problems with this tightness are not path consistent [van Beek, 1994].

In Table 3. we have the results of experiments of run­ ning GSAT with and without a preprocessing algorithm BR-3 on uniform random 3SAT formulas with N = 600 variables and C = 2550 constraints (note that this class of 3SAT formulas contains both consistent and incon­ sistent problems). Unlike RBR-3 which resolves only original clauses, RB-3 computes a closure under Bound3 resolution. In this case GSAT with BR-3 was even slightly worse than just GSAT in terms of the number of problems solved, although GSAT with BR-3 used fewer flips and was slightly faster. We also tried the Davis­ Putnam procedure, but it took far too long.

6 Conclusions

In this paper we focused on the problem of how prepro­ cessing improves the performance of GSAT. In partic­ ular , we have investigated the effect of enforcing a cer­ tain degree of local consistency, as a preprocessing step, on two different classes of problems - random uniform problems that do not have any structure and random structured problems. The effect of local consistency is sharply different on these two classes of problems.

Our experiments show that when problems do not have any special structure, local consistency does not have a significant effect on the performance of GSAT. Even disregarding the cost of preprocessing, GSAT was frequently less effective on the preprocessed problem. However, on certain classes of structured problems, local consistency can significantly improve the performance of GSAT.

We have shown that there are structured problems that are extremely hard for GSAT while easy for the Davis-Putnam procedure. These problems are so hard that even heuristics like clause weighting which was orig­ inally designed to help escape local minimums caused by the special structure of the problem do not seem to help much. The characteristic feature of these problems is the presence of tightly connected clusters of variables which, in turn, are loosely connected by another set of global constraints.

This class of problems was first discovered by Kono­ lige [Konolige, 1994] . In this paper we have shown how to deal with these kinds of problems. Our experiments show that enforcing local consistency, like bounded reso­ lution, can make these problems almost trivial for GSAT. The overhead associated with enforcing this kind of local consistency is much less than the computation needed to solve the problem without it.

Acknowledgments

We would like to thank Irina Rish for running experi­ ments with the Davis-Putnam procedure, and Dan Frost for letting us use his backjumping algorithm with dy­ namic variable ordering. We would also like to thank Steve Hampson for interesting and stimulating discus­ sions on GSAT.