benchmarks. The y-axes represent the solving time (or nodes visited) for the Impact heuristic and the x-axes the corresponding values for the *dom/wdeg* heuristic (Figures (a) and (b)), "*alldell*" heuristic (Figures (c) and (d)) and "*fully assigned*" heuristic (Figures (e) and (f)). Therefore, a point above line y = x represents an instance which is solved faster (or with less node visits)
using one of the conflict-driven heuristics. Both axes are logarithmic.

As we can clearly see from Figure 1 (left plots), conflict-driven heuristics are almost always faster. Concerning the numbers of visited nodes, the right plots do not reflect an identical performance. Although it seems that in most cases conflict-driven heuristics are making a better exploration in the search tree, there is a considerable set of instances where the Impact heuristic visit less nodes.

The main reason for this variation in performance (cpu time versus nodes visited) that the impact heuristic has, is the time consuming process of initialization. The idea of detecting choices which are responsible for the strongest domain reduction is quite good. This is verified by the left plots of Figure 1. But the additional computational overhead of computing the "best" choices, really affect the overall performance of the impact heuristic (Figure 1, right plots). As our experiments showed the impact heuristic cannot handle efficiently problems which include variables with relatively large domains. For example in the RLFA
problems where we have 680 variables with at most 44 values in their domains results in Table 2 verified our hypothesis. On the other hand in problems where variables have only a few values in their domains (as in the Boolean instances of Section 4.6) results showed that the impact heuristic is quite competitive.

Finally, it has to be noted that the dominant conflict-driven heuristics are generic and can be also applied in solvers that use 2-way branching and make heavy use of propagators2for global constraints, as do most commercial solvers.

In the case of 2-way branching the heuristics can be applied in exactly the same way as in d-way branching. In the case of global constraints simple modifications may be necessary, for example to associate each constraint with a weight independent from the propagator chosen for the constraint. But having said these, it remains to be verified experimentally whether the presence of global constraints or the application of 2-way instead of d-way branching influence the relevant performance of the heuristics.

## 5. Conflict-Driven Revision Ordering Heuristics

Having demonstrated that conflict-driven heuristics such as *dom/wdeg* are the dominant modern variable ordering heuristics, we turn our attention to the use of failures discovered during search in a different context. To be precise, we investigate their use in devising heuristics for the ordering of the (G)AC revision list.