Optimal Refutations for Constraint Satisfaction Problems

1 Introduction

The conventional wisdom in systematic backtrack search is that a variable ordering heuristic should be chosen so that if a bad assignment is made, and search enters an insoluble (sub)tree, the heuristic will prefer variables that have a high likelihood of proving quickly that the current (sub)tree is indeed unproductive. This property of a variable ordering heuristic is often referred to as failfirstness [Haralick and Elliott, 1980]. Fail-�rstness can be seen as an explanation for why particular variable ordering heuristics are better than others for solving CSPs, and it has received considerable attention from the research community [Smith and Grant, 1998; Beck et al., 2004]. Various ways of explaining the quality of variable ordering heuristics in terms of fail-�rstness have been proposed. Some authors argue that heuristics that minimise branching depth are best [Haralick and Elliott, 1980], while others argue that such a policy can cause an increase in branching factor which can have the effect of increasing the size of the resultant (sub)tree [Smith and Grant, 1998].

A search algorithm enters an insoluble search tree either because the problem itself is insoluble, or because the current partial solution has just been extended with an assignment that cannot lead to a complete solution. In either case, the ideal is that insolubility can be proven with the least amount of effort. In this paper we will measure such effort by the number of nodes visited to prove that an insoluble (sub)tree has no solution. We can evaluate variable ordering heuristics by comparing the number of nodes that they visit to prove the insolubility of a (sub)problem with the minimum number of nodes required to draw the same conclusion.

By comparing optimal refutations with those generated by MAC [Sabin and Freuder, 1994], when combined with various standard variable ordering heuristics, we show empirically that there is a signi�cant difference between the performance of heuristics on typical random problems and those found in the real world. We also suggest that small-tomedium sized random binary CSPs are of limited value when studying and developing variable ordering heuristics. While this has been the intuition amongst constraints researchers, our analysis shows empirically that this is indeed the case and gains insights into the nature of the difference in behaviour between random and real-world problems. Finally, we discuss how our results may provide further insights into the causes of the heavy-tailed phenomenon observed in the runtime distributions of backtrack search procedures. For example, by focusing on the distributions of actual and optimal refutations we can study whether heavy-tailedness is present because of the variable ordering heuristic, the value ordering heuristic, or is more fundamentally related to the structure of the problem.

2 Preliminaries

Definition 1 (Constraint Satisfaction Problem). We define a CSP as a 3-tuple P ˆ= 〈V,D,C〉 where V is a finite set of n variables V ˆ= {V1, . . . , Vn}, D is a set of finite domains D ˆ= {D(V1), . . . , D(Vn)} such that D(Vi) is the finite set of possible values for Vi, and C is a finite set of constraints such that each Cij ∈ C is a subset of D(Vi) ×D(Vj) specifying the combinations of values allowed between Vi and Vj , where i < j. We say that P is arc-consistent (AC) if ∀vk ∈ D(Vi) and ∀j such that Cij ∈ C, ∃vl ∈ D(Vj ) with (vk, vl) ∈ Cij . An assignment Aik ˆ= 〈Vi = vk〉 represents a reduction of D(Vi) to {vk} ⊆ D(Vi). A solution to P is a set of distinct assignments S ˆ= {Al1k1 , . . . , Alnkn |(vki , vkj ) ∈ Cij}.

Definition 2 (Search Algorithm). A search algorithm Θ ˆ= 〈Λ, ∆, ≺V , ≺v〉 is a combination of a branching method Λ, a consistency enforcement method ∆, a variable ordering ≺V and a value ordering ≺v, both of which can be either static or dynamic.

Definition 3 (Search Tree). A search tree T for a problem P is a set of nodes and arcs. Each node corresponds to a set of assignments, N ˆ= {Al1k1 , . . . ,Alp-1kp-1 ,Alpkp }, totally ordered by a dynamic variable ordering heuristic ≺V . The root of the search tree is a special node R ˆ= ∅. Two nodes N1 and N2 are connected by an arc if ∃Aij such that N2 = N1 ∪ Aij , in which case we say that N1 is the parent of N2, and N2 is the child of N1. For every node N, its children are totally ordered by a dynamic value ordering heuristic ≺v.

Search trees are de�ned in the context of a speci�c search algorithm. For a particular CSP instance P, and search algorithm Θ, a one-to-one mapping exists between the nodes in the search tree T and the assignments made by Θ.

Definition 4 (Mistake Point). For a soluble problem P, a mistake point M is a node identified by a set of assignments M ˆ= {Al1k1 , ...,Alp-1kp-1 ,Alpkp }, totally ordered by ≺V , for which ∃S ∈ S such that M \ {Alpkp } ⊂ S, but ¬∃S ∈ S such that M ⊂ S. Since an insoluble problem does not admit any solutions, we define the mistake point associated with an insoluble problem as the root of its search tree.

Informally, a mistake point corresponds to an assignment that, given past assignments, cannot lead to a solution even though, in the case of a soluble problem, a solution exists. Whenever the value ordering heuristic makes such a mistake, the role of the variable ordering heuristic is to guide the search out of that insoluble search tree as quickly as possible. However, it is important to realise that the actual set of mistake points encountered during search is also dependent on the variable ordering heuristic used.

For a soluble problem P, let PM ˆ= {VM,DM,CM} be the insoluble (sub)problem corresponding to M, where VM ˆ= V \ {Vl1 , ..., Vlp }, CM ˆ= {Cij |Vi, Vj ∈ VM, Cij ∈ C}, and DM is the set of current domains after arc-consistency has been restored to re�ect the domain reductions due to M. If P is insoluble, as a notational convenience, we de�ne M ˆ= ∅ and PM as the arc-consistent version of P. For brevity, we will refer to the insoluble (sub)tree rooted at a mistake point and its corresponding insoluble (sub)problem interchangeably.

Definition 5 (Refutations). Given a search algorithm Θ, a refutation for a given insoluble (sub)problem PM, rooted at mistake point, M, is simply the corresponding search tree TM. We will refer to |TM|, the number of nodes in TM, as the size of the refutation.

We study the refutations found using a version of MAC that uses AC-3 [Mackworth, 1977] for consistency enforcement and selects values randomly. Our goal is to determine how close to optimality are the refutations obtained when well known variable ordering heuristics, with randomly broken ties, are substituted for ≺V . For each heuristic ≺V we �rst collect the mistake points it generates when using MAC

(note that each variable ordering heuristic will generate a different set of mistake points). When we analyse MAC in conjunction with a certain ≺V on a mistake point M, we will refer to the refutation for the (sub)problemPM as the actual refutation. We will contrast the actual refutation with the optimal refutation for PM, obtained by replacing ≺V with a new variable ordering heuristic ≺V such that |TM| is minimised.

Sometimes, rather than using the optimal refutation, we compare against the quasi-optimal, de�ned as the smallest refutation whose depth does not exceed that of the actual. By selecting variables based on a depth-�rst traversal of the tree of minimum size, ≺V causes MAC to generate the smallest possible search tree proving insolubility for PM. In our experience it is extremely rare that the quasi-optimal refutation is larger than the optimal. By accepting quasi-optimality we can use the depth of the actual refutation as an upper bound, dramatically speeding-up search for better refutations.

Definition 6 (Improvement Ratios). For a given mistake point, the refutation improvement ratio is the ratio between the size of the actual refutation and that of the optimal refutation. The overall refutation improvement ratio is simply the ratio between the total number of nodes in all the actual refutations and the total number of nodes in all their corresponding optimal refutations encountered when finding the first solution or proving insolubility.

3 Analysing Refutations

Our focus here is only on how a variable ordering heuristic behaves when trying to prove insolubility for a (sub)problem. We are not interested in focusing on how often a variable ordering heuristic enters an insoluble (sub)tree. Therefore, our analysis is centered around �nding optimal refutations for all the mistake points in a search tree. Unfortunately, this is a herculean task, as we have to search through all the possible permutations of assignments, i.e. consider all possible search trees rooted at each mistake point. Without clever optimisations, this would not be feasible for anything but the tiniest problems.

3.1 Basic Algorithm

Given a problem instance, a search algorithm (MAC in our case) and the variable ordering heuristic to be evaluated, we begin by searching for a solution, with the goal of identifying all the mistake points. The mistake points represent the roots of the insoluble (sub)trees the search algorithm happens to encounter before �nding the �rst solution. For each such mistake point we compute both the actual refutation, by rerunning MAC on the current (sub)problem using the heuristic we are evaluating, and the optimal refutation, by considering all the possible permutations of assignments to the variables involved in that (sub)problem. Note that insoluble instances are just a special case where the only mistake point is before the �rst assignment. Furthermore, when analysing insoluble problems, it is important to realise that the optimal refutation is independent of the heuristic used; in other words no other ordering could possibly prove insolubility more quickly.

Both the search algorithm with the variable ordering heuristics being analysed and the exhaustive search for the optimal refutation use the same method of enforcing consistency (AC in our case). Failure to do so would make the refutation improvement ratio a function of both the variable ordering and the level of consistency enforced, thus being detrimental to our goal of analysing variable ordering heuristics.

The version of MAC that we use employs k-way branching [Smith and Sturdy, 2004], rather than binary branching, so that selecting a variable Vi creates |D(Vi)| branches in the search tree. Thus, we make sure that refutation sizes are not in�uenced by the value ordering.

3.2 Optimisations

There are a number of optimisations that we have applied.

Secondly, we can improve the search by looking ahead to avoid choices that cannot improve on the current smallest refutation. Whenever a variable Vi is selected at a certain depth all the values in its domain have to be tried, and they all have to fail for the current (sub)problem to be proved insoluble. Consequently, we know that by selecting Vi, the size of the current partial refutation will increase by at least a number of nodes equal to |D(Vi)|. We call this a 1-level look-ahead.

Firstly, we can easily maintain an upper bound on the size of the optimal refutation by initially setting it to the size of the actual refutation, then updating it as smaller refutations are found. Therefore, the search for the optimal refutation can be implemented as a branch-and-bound procedure.

By temporarily assigning to Vi, in turn, every value v in its domain, and by attempting to restore arc-consistency after every such assignment, we can associate with each v a minimum contribution to the size of the refutation. If the assignment makes the subproblem arc-inconsistent, v's contribution will be 1, given by the node corresponding to the assignment itself. However, if arc-consistency can be restored after the assignment, at least one more variable will have to be considered before the current subproblem can be proved insoluble. Therefore, v will carry a minimum contribution equal to the smallest domain size amongst all the remaining unassigned variables. We call this a 2-level look-ahead.

In general, Vi's selection would increase the size of the current partial refutation by at least the sum of the minimum contributions of all the values in its domain. If that would cause the current partial refutation to exceed the size of the smallest refutation found so far, Vi will be skipped at the current depth. This dramatically reduces the search space and brings reasonable size problems within reach.

4 Experiments

The basic experiment we run is this: for each variable ordering heuristic we �rst �nd all the mistake points that MAC visits when �nding the �rst solution or proving insolubility; for each mistake point, we �nd MAC's actual refutation (still with the same heuristic); using the size of the actual refutation as an upper bound, we �nd the (quasi-)optimal refutation. This approach was adopted because different variable orderings generate potentially different sets of mistake points.

We have performed experiments 1 on random binary problems, various instances of the n-queens problem for varying values of n, and a subset of the RLFAP Celar Scen11 [Cabon et al., 1999]. We have studied the following dynamic variable ordering heuristics: min-domain [Haralick and Elliott, 1980], max-degree, min(domain/degree) [Bessi�ere and Regin, 1996], and brelaz [Br·elaz, 1979]; their corresponding anti-heuristics; and random variable selection. These are regarded as the standard general-purpose variable ordering heuristics used in the CSP literature. Ties were broken randomly. Throughout our experiments we have used a dynamic random value ordering.

1 Code freely available with source at http://hulubei.net/tudor/csp.

Note that for heuristics we report the optimal refutations for random problems and n-queens, and the quasi-optimal refutations for RLFAP. For anti-heuristics we always compute quasi-optimal refutations. While the true optimal refutations for RLFAP may be smaller than those reported, based on our observations the difference is not signi�cant. Limiting the search to quasi-optimal proofs allowed us to gather signi�cantly more data for this problem.

4.1 Random and n-Queens Problems

Due to the extreme computational requirements of the search for optimal refutations, we had to limit our experiments to random problems with 15 variables and uniform domain sizes of 10 values. We generated 800 instances for each tightness point using a random problem generator that conforms to the Model-B speci�cation [Gent et al., 2001].

We selected instances at the highest peak of dif�culty for these problems, found to pass through a plane corresponding to density 0.95. Tightness was varied along this plane. Specifically, we identify a distinct tightness at which we move from generating a set of problem instances that are all soluble to generating instances that are all insoluble. In Figure 1 this transition occurs at a tightness of 0.3. We indicate the range of tightness for which all problems were soluble (resp. insoluble) with a �high� (resp. �low�) line.

In Figure 1 we present the results associated with each of the variable ordering heuristics studied. Note that we are not ranking heuristics, but are simply studying how close their actual refutation sizes are to optimality. The overall refutation improvement ratio peaks at 1.8 for min(domain/degree) at a tightness of about 0.24, meaning that for the set of mistake points encountered when solving these problems using min(domain/degree) there does not exist a variable ordering that could decrease the number of nodes in the corresponding refutations by more than that factor, on the average. Since at the peak of dif�culty proving insolubility accounts for most of the time spent in search, this result suggests that no improvement in the ordering of variables, for the problems we have studied, would ever lead to an order of magnitude speedup. Indeed, in the soluble region we can see that at best we can hope to halve the time taken by max-degree. In theory, however, for soluble problems heuristics could do better by failing less.

Once we move through the phase-transition to insoluble problems, all heuristics offer improvement ratios less than 2.2 for max-degree and less than 1.6 for all other heuristics, except random. In the case of min(domain/degree) we see that when using MAC at the peak of dif�culty the ratio is approximately 1.4. This is an interesting result since is demonstrates that for proving insolubility no variable ordering heuristic exists, for these problems, that can improve upon min(domain/degree) by more than a factor of 1.4 at the peak of dif�culty.

Figure 2 presents a plot of the distribution of actual refutation sizes against optimal, per mistake point, for the random and min(domain/degree) variable ordering heuristics. Of interest here is the apparent linear relationship between actual versus optimal refutation size. A similar linear relationship was observed for all other heuristics and anti-heuristics studied. When we discuss the performance of variable ordering heuristics on a real-world problem in the next section we will see that this linear relationship does not hold and that for very large refutations found by a heuristic, the optimal refutation can be many orders of magnitude smaller.

The performance of a random variable ordering is of comparable quality to that of a good variable ordering heuristic in this problem class. From Figure 1 we see that the improvement ratio of the random heuristic is approximately 2.7 at the phase transition, close to that of standard heuristics.

Finally, in Figure 3 we present, for each variable ordering heuristic, the distribution of insoluble (sub)trees in the dataset as a function of the improvement ratio. We see that almost all ratios were close to 1, meaning that almost all of the time the standard variable ordering heuristics performed very close to perfection. We also see that for the random ordering heuristic ratios of 10 are found less that 0.01% of the time and that there does not exist a single insoluble (sub)tree that provides an opportunity to make improvements of more than an order of magnitude over current heuristics.

In experiments performed over a large data-set of insoluble subtrees generated from problems ranging from 8 to 22 queens we have observed similarly small refutation improvement ratios for n-queens, only slightly bigger than those observed for random problems. Also, the linear relationship between actual and optimal refutation size was observed, as well as a similar distribution of ratios.

4.2 RLFAPCelar Scen11

The small improvement ratios obtained for random problems and n-queens, and estimated in [Li and G·erard, 2000] for hard random unsatis�able 3-SAT, do not seem to hold for real-world problems. A popular benchmark for binary CSPs, RLFAP Celar Scen11 was an obvious candidate for our analysis. Unfortunately, at 680 variables, we could not analyse the entire problem. Instead, we extracted a subset of the original problem made up of 22 variables that were part of the backdoor set [Williams et al., 2003] over which MAC backtracked while solving the original problem. We analysed all the mistake points found when solving this subset of RLFAP over 500 times for all variable ordering heuristics.

However, of particular interest in this problem is the pattern we observe in Figure 5. While the vast majority of refutations

Refutation improvement ratios of 20 and over were observed, even when using the best heuristics, as seen in Figures 4 and 5, while they were non-existent for random and nqueens problems. Comparing Figures 2 and 4 we can clearly see that heuristics behaves very differently on this problem than on the random problems presented earlier. Speci�cally, we can see that actual refutations correlate very poorly with quasi-optimal and that no linear relationship exists; note that a log-scale had to be used on the y-axis of the left plot in Figure 4 due to the spread of actual refutation sizes for each quasi-optimal point on the x-axis.

offer small improvement ratios, it is possible to �nd subtrees on which the standard heuristics perform very poorly. For example, we can see that in a small number of subtrees maxdegree did 100 times worse than quasi-optimal, while the other heuristics, except min(domain/degree), sometimes did 50 times worse than quasi-optimal. Clearly, the behaviour of standard variable orderings is signi�cantly different on realworld problems than on the random problems that many researchers use as a basis for studying these heuristics. In the case of a random variable ordering, we observed a very small number of subtrees where the refutation found was more than a factor of 105 worse than quasi-optimal, and that in the vast majority of cases it performed more than an order of magnitude worse than quasi-optimal.

Therefore, our standard heuristics behave very differently, indeed much worse, on real-world problems than on random and n-queens problems. In particular, they can be less robust in the sense that they can sometime waste signi�cant amounts of time �nding refutations for insoluble (sub)trees that are far worse than optimal.

5 Discussion

It is clear from our analysis that the standard variable orderings used to solve CSPs behave very differently on realworld problems than on random problems of comparable size, which are frequently used to study the performance of heuristics in the research literature. Our results demonstrate that there are considerable opportunities to improve search performance on real-world problems. Some researchers have already begun developing the necessary infrastructure needed to study real-world problems in a systematic way [Gomes et al., 2000; Walsh, 1999; Walsh, 2001]. There have also been some recent successful results demonstrating that one can bene�t considerably from developing variable ordering heuristics that can exploit characteristics one encounters in real-world problems [Boussemart et al., 2004; Dubois and Dequen, 2001; Refalo, 2004].

Our analysis is related to the work of Li and Gerard on studying the limits of branching heuristics for random 3-SAT [Li and G·erard, 2000]. However, our interests here are in studying the limits of variable ordering heuristics in a constraint satisfaction context. Furthermore, our analysis is capable of �nding exact optimal refutations, rather than approximating them, and focuses on the differences observed between random and real-world problems. Our work is also closely related to the theoretical analysis of proof complexity for satis�ability and constraint satisfaction [Beame et al., 1998; Mitchell, 2003].

It is not known whether the linear relationship between actual and optimal refutations is preserved as the size of random problems increases. Recent work on studying the performance of variable ordering heuristics on very large CSPs has shown that there can be orders of magnitude differences between heuristics [Bessi�ere et al., 2001]. However, those results do not contradict the results presented in this paper with respect to the relative performance of standard variable orderings on random and non-random problems.

In this paper we introduce a potentially useful tool for analysing the causes of the heavy-tailed phenomenon observed in the runtime distributions of backtrack search procedures [Gomes et al., 2000]. Figures 5 and 6 show, for RLFAP, a very small percentage of insoluble (sub)problems for which standard variable ordering heuristics will �nd refutations that are signi�cantly larger than optimal, leading to a long runtime. Furthermore, it is also interesting to note from Figure 5 that the vast majority of actual refutations are very close to being optimal, with the exception of those found with a random variable ordering heuristic.

Gomes et al. [2004] report a high correlation between the distribution of the depth of mistake points and the runtime distribution, e.g. the presence of heavy-tails. We can further extend this analysis by also considering the size of optimal refutations rooted at these mistake points. This may provide a way of isolating the causes of heavy-tailed behaviour by making a distinction between the effects of the algorithm and its components (propagation method, variable and value orderings), versus the effects of the inherent structure of the problem [Walsh, 1999; Walsh, 2001]. As part of our future work in this area we will study optimal refutations for problems that are well known to exhibit heavy-tail behaviour.

6 Conclusions

In this paper we have proposed a novel approach to empirically looking at problem hardness and typical-case complexity by comparing optimal refutations with those generated by standard search heuristics. We have compared refutations of insoluble (sub)trees found using well known variable ordering heuristics combined with a standard CSP search algorithm against optimal refutations. Our results show that there is a signi�cant difference between the performance of heuristics on typical random problems and those found in the realworld. We suggest that small-to-medium sized random binary CSPs are of limited value to constraints researchers and introduced a potentially useful tool for analysing the causes of the heavy-tailed phenomenon observed in the runtime distributions of backtrack search procedures.

Acknowledgments

This material is based on work supported by Science Foundation Ireland under Grant 00/PI.1/C075. We would like to thank Barbara M. Smith, Eugene C. Freuder, Nic Wilson, Chris Beck, Bart Selman, Carla Gomes and Susan Epstein for their comments and suggestions, and to John Morrison and the Boole Centre For Research in Informatics for providing access to their Beowulf cluster.