likely that the domains of the variables are of equal size, ties are frequently noticed. A common tie breaker for the dom heuristic is *lexico*, (*dom+lexico* composed heuristic) which selects among the variables with smallest domain size the lexicographically first. Other known composed heuristics are *dom+deg* [18], *dom+ddeg* [9, 35] and BZ3 [35].

Bessi`ere et al. [3], have proposed a general formulation of DVOs which integrates in the selection function a measure of the constrainedness of the given variable. These heuristics (denoted as *mDVO*) take into account the variable's neighborhood and they can be considered as neighborhood generalizations of the dom and *dom/ddeg* heuristics. For instance, the selection function for variable Xiis described as follows:

$$H_{a}^{\otimes}(x_{i})={\frac{\sum_{x_{j}\in\Gamma(x_{i})}\left(\alpha(x_{i})\otimes\alpha(x_{j})\right)}{|\Gamma(x_{i})|^{2}}}$$
$$(1)$$

2(1)
where Γ(xi) is the set of variables that share a constraint with xi and α(xi)
can be any simple syntactical property of the variable such as |D(xi)| or |D(xi)| |Γ(xi)| and } ∈ {+, ×}. Neighborhood based heuristics have shown to be quite promising.

Boussemart et al. [8], inspired from SAT (satisfiability testing) solvers like Chaff [29], proposed conflict-driven variable ordering heuristics. In these heuristics, every time a constraint causes a failure (i.e. a domain wipeout) during search, its weight is incremented by one. Each variable has a *weighted degree*,
which is the sum of the weights over all constraints in which this variable participates. The weighted degree heuristic (*wdeg*) selects the variable with the largest weighted degree. The current domain of the variable can also be incorporated to give the domain-over-weighted-degree heuristic (*dom/wdeg*) which selects the variable with minimum ratio between current domain size and weighted degree.

Both of these heuristics (especially *dom/wdeg*) have been shown to be very effective on a wide range of problems.

Grimes and Wallace [21, 39] proposed alternative conflict-driven heuristics that consider value deletions as the basic propagation events associated with constraint weights. That is, the weight of a constraint is incremented each time the constraint causes one or more value deletions. They also used a sampling technique called *random probing* where several short runs of the search algorithm are made to initialize the constraint weights prior to the final run. Using this method *global contention*, i.e. contention that holds across the entire search space, can be uncovered.

Inspired by integer programming, Refalo introduced an *impact* measure with the aim of detecting choices which result in the strongest search space reduction
[31]. An impact is an estimation of the importance of a value assignment for reducing the search space. Refalo proposes to characterize the impact of a decision by computing the Cartesian product of the domains before and after the considered decision. The impacts of assignments for every value can be approximated by the use of averaged values at the current level of observation.

If K is the index set of impacts observed so far for assignment xi = α, I is the