averaged impact:

 $ \frac{\sum_{k\in K}I^k(x_i=\alpha)}{|K|}$                 (2)  and value impact for any $ k\in K$. 
$$\left({\boldsymbol{3}}\right)$$
7
where I
kis the observed value impact for any k ∈ K.

The impact of a variable xi can be computed by the following equation:

$$I(x_{i})=\sum_{\alpha\in D(x_{i})}1-{\overline{{I}}}(x_{i}=\alpha)$$

An interesting extension of the above heuristic is the use of "node impacts" to break ties in a subset of variables that have equivalent impacts. Node impacts are the accurate impact values which can be computed for any variable by trying all possible assignments.

Correia and Barahona [13] proposed variable orderings, by integrating Singleton Consistency propagation procedures with look-ahead heuristics. This heuristic is similar to "node impacts", but instead of computing the accurate impacts, it computes the reduction in the search space after the application of Restricted Singleton Consistency (RSC) [30], for every value of the current variable. Although this heuristic was firstly introduced to break ties in variables with current domain size equal to 2, it can also be used as a tie breaker for any other variable ordering heuristic.

Cambazard and Jussien [11] went a step further by analyzing where the reduction of the search space occurs and how past choices are involved in this reduction. This is implemented through the use of *explanations*. An explanation consists of a set of constraints C
0(a subset of the set C of the original constraints of the problem) and a set of decisions dc1*, ..., dc*n taken during search.

Zanarini and Pesant [42] proposed *constraint-centered heuristics* which guide the exploration of the search space toward areas that are likely to contain a high number of solutions. These heuristics are based on solution counting information at the level of individual constraints. Although the cost of computing the solution counting information is in general large, it has been shown that for certain widely-used global constraints, such information can be computed efficiently.

Finally, we proposed [2] new variants of conflict-driven heuristics. These variants differ from *wdeg* in the way they assign weights. They propose heuristics that record the constraint that is responsible for any value deletion during search, heuristics that give greater importance to recent conflicts, and finally heuristics that try to identify contentious constraints by detecting all possible conflicts after a failure. The last heuristic, called "fully assigned", increases the weights of constraints that are responsible for a DWO by one (as *wdeg* heuristic does) and also, only for revision lists that lead to a DWO, increases by one the weights of constraints that participate in fruitful revisions (revisions that delete at least one value). Hence, this heuristic records all variables that delete at least