rather that trying the next value of the current one. Following the above intuitions we propose two generic heuristics:
Hsdif f (e) :- VOH score difference If the current variable is x and the VOH suggests to branch on a different variable y**, we will follow this suggestion only when**
|score(y) − score(x)| > e, where score(x) and score(y**) are** the values assigned by the VOH to variables x and y**, while** e is a threshold value difference.

Hcadv(VOH2) : - complementary advisor **If the current**
variable is x and the VOH used by the algorithm (V OH1) suggests to branch on a different variable y**, we will follow this**
suggestion only when a secondary VOH (V OH2**) also prefers**
y to x. That is, when score**V OH**2
(y) > score**V OH**2
(x**), where**
score**V OH**2
(x) and score**V OH**2
(y) are the heuristic values assigned by V OH2 to variables x and y 3
.

Both proposed heuristics are generic, in the sense that they can be used in tandem with any VOH and any backtracking search algorithm. However, Hsdif f (e**) requires some tuning to**
set the value of e appropriately. In contrast, Hcadv(**V OH**2)
does not require any such tuning, and can use any VOH as a secondary heuristic. The two heuristics can also be combined either conjunctively or disjunctively. In the former (resp. latter) case, the suggestion to branch on a variable different than x **is followed when both (resp. at least one) of the criterions**
for Hsdif f and Hcadv are satisfied. Importantly, the two proposed heuristics are lightweight, assuming that V OH2 **is not**
too expensive to compute.

## 5 Experiments

In this section we evaluate the performance of the two heuristics on a variety of CSP instances. Before presenting the results, we discuss the tuning of heuristic H**sdif f** (e).

## 5.1 Tuning Heuristic H**Sdif F** (E)

Although heuristic Hsdif f (e) is generic and can be used together with any VOH, the optimum threshold value e obviously varies among different VOHs as they may consider different metrics, such as domain sizes, constraint degrees, constraint weights, etc. Even with a fixed VOH and within a specific problem class, the optimum threshold value e **may differ**
from instance to instance, and therefore locating it is not particularly interesting from a practical point of view. However, our experiments have demonstrated that a "good enough" value for e **that carries across different problem classes can be** located for a given VOH with only a few experiments.

To find a good value for e **we proceeded as follows. Taking a**
single instance from some problem class we repeatedly solved it using the Hsdif f (e**) heuristic for branching, starting with** e set to 0 and gradually increasing e **in every repetition. Setting**
e = 0 forces Hsdif f (e**) to emulate 2-way branching, while as** e increases, Hsdif f (e**) moves closer to restricted 2-way branching. For each run we measured the number of times when,**
after a failed assignment x = ai and the successful propagation of x 6= ai, the VOH chose to branch on a variable y **other**
than x. In the following we will call this measure **variable**
changes (vc**). By definition, such a situation does not occur** with restricted 2-way branching, hence with this branching scheme vc **is always 0.**
3 We assume that a greater score is better according to **V OH**2.

Specifically for dom/wdeg, the value of e **was increased in**
steps of 0.01. Figures 2b, c and d show the number of nodes (yaxis) as a relation of e (x**-axis) for instances scen11, series12**
and haystacks-05 respectively. The first data point in these plots (where e **= 0) essentially gives the number of nodes for** 2-way branching. The experiment was stopped when for some value of e the observed value of vc **was 0. The last data point** in each plot, corresponding to this situation, essentially **gives**
the number of nodes for restricted 2-way branching.

![0_image_0.png](0_image_0.png)

In Figures 2b and c (scen11 and series12), where 2-way branching is better than its restricted version, we can notice that as e **increases there is point where a sharp decline in the**
performance of Hsdif f (e**) occurs. Respectively, in Figure 2d**
(haystacks-05) where restricted 2-way is better, we can notice that as e **increases there is point where a sharp improvement in the performance occurs. After running similar experiments with benchmark instances from other problem classes,**
we observed that setting e to values around 0.1, when using dom/wdeg **for variable ordering, gives good results across**
many different instances and problem classes. For heuristic dom/alldel **this value was 0.001.**
Finally, Figure 2a gives the recorded value of vc (y**-axis)**
as a relation of e (x**-axis) for the RLFAP instance scen11.**
Not surprisingly, as the value of e **increases, the value of** vc decreases. Interestingly, there is a sharp (exponential) decline in the value of vc roughly around the point where e = 0.**1. A**
similar phenomenon was observed in all the tested instances.

## 5.2 Experimental Evaluation

We have experimented with 400 instances from the problem classes detailed in Section 3. We compared the performance