with four VOHs: dom, dom/ddeg, dom/wdeg, and **dom/alldel**.

Benchmarks are taken from the web page of C. Lecoutre, where details about them can be found. The following classes of binary and non-binary problems have been used: radio links frequency assignment (RLFAP), driver, ehi, geom, graph coloring, quasigroup completion, chessboard coloration, **allinterval series, golomb ruler and random instances from the**
RB model (forced to be satisfiable).

Results from the use of dom **with the three branching**
schemes showed that under this heuristic 2-way branching essentially emulates d**-way branching and the three branching**
schemes are closely matched in terms of run times (with d**way being slightly better). This is in accordance with previous**
results [6].

Table 1. **CPU times (t) in secs. and nodes (n) for the three**

branching schemes using the VOH **dom/ddeg**.

Instance 2 − way restricted d − way

2 − way

scen-11 t 7.1 508 372

(sat) n 1379 68597 45862

scen-11-f11 t 8.1 > 1h > 1h

(**unsat**) n 2716 - -

driverlogw-09 t 205 1197 1207

(sat) n 75033 0.42M 0.16M

ehi-85-297-0 t 62.3 2509 2481

(**unsat**) n 37246 2.5M 0.9M

ehi-85-297-2 t 41.8 > 1h > 1h

(**unsat**) n 20733 - -

ash958GPIA-4 t 5.1 > 1h > 1h

(sat) n 2712 - -

cc-12-12-2 t 58.3 978 959

(**unsat**) n 36994 0.56M 0.27M

In Table 1 we give indicative results from the use of the dom/ddeg **heuristic. We display CPU times as well as nodes.** A node in 2-way branching can be a value assignment or a value removal, while in d**-way branching it can only be a**
value assignment. Hence, they cannot be compared directly.

However, nodes give an accurate measure of the difference in search effort between 2-way and restricted 2-way. Our experiments confirm the theoretical results of [5] as we can observe huge differences in favor of 2-way branching. Restricted 2-way and d**-way display similar performance.**
Table 2 compares the three branching schemes when using the conflict-driven VOH dom/wdeg**. As this heuristic can**
learn from failures (DWOs) encountered during search, and thus make more informed choices, it significantly outperforms dom/ddeg **[2]. Comparing these results with the results of Table 1, we can notice two differences: First, there are instances**
where 2-way branching is less efficient, sometimes considerably, compared to restricted 2-way and d**-way. Second, in instances where 2-way branching dominates, the differences are**
not as striking as in Table 1, albeit they can still be considerable. Quantitatively similar results were observed when using the conflict-driven VOH **dom/alldel**.

In the first part of Table 2 we group representative instances where 2-way branching is the best choice, while in the second part we show results where restricted 2-way and d-way are better. Neither 2-way nor d**-way (and restricted 2-way) is the**
best choice, even for instances within the same problem class
(see for example the ruler25 and frb35-17 problems in Table 2). As in the case of dom/ddeg**, restricted 2-way branching**
displays a behavior very close to that of d**-way branching.**

| branching schemes using the VOH dom/wdeg. Instance 2 − way restricted   | d − way   |        |        |        |
|-------------------------------------------------------------------------|-----------|--------|--------|--------|
| 2 − way                                                                 |           |        |        |        |
| series-12                                                               | t         | 27.3   | 145.7  | 158.5  |
| (sat)                                                                   | n         | 33876  | 245787 | 246379 |
| series-13                                                               | t         | 148.4  | 1132   | 1057   |
| (sat)                                                                   | n         | 150145 | 1.6M   | 1.3M   |
| scen11                                                                  | t         | 12.6   | 45.1   | 34.2   |
| (sat)                                                                   | n         | 2414   | 6002   | 4398   |
| scen2-f25                                                               | t         | 42.3   | 183.8  | 137.9  |
| (unsat)                                                                 | n         | 9539   | 38185  | 50609  |
| graph9-f9                                                               | t         | 178.6  | 640.5  | 923    |
| (unsat)                                                                 | n         | 66367  | 255204 | 406361 |
| ruler-25-8-a3                                                           | t         | 50.3   | 180.8  | 167.6  |
| (unsat)                                                                 | n         | 1829   | 6407   | 7026   |
| frb35-17-1                                                              | t         | 34.2   | 135    | 114    |
| (sat)                                                                   | n         | 11129  | 54026  | 40165  |
| geo50-20-d4-75-1                                                        | t         | 2298   | 1242   | 1128   |
| (sat)                                                                   | n         | 558754 | 279998 | 257225 |
| geo50-20-d4-75-2                                                        | t         | 122    | 28,5   | 28.3   |
| (sat)                                                                   | n         | 48943  | 9153   | 9509   |
| haystacks-05                                                            | t         | 41.7   | 3.9    | 3.7    |
| (unsat)                                                                 | n         | 1.78M  | 0.18M  | 0.16M  |
| qcp-15-120-5                                                            | t         | 529    | 408    | 402    |
| (sat)                                                                   | n         | 0.76M  | 0.63M  | 0.25M  |
| abb313GPIA-7                                                            | t         | 498    | 313    | 309    |
| (unsat)                                                                 | n         | 28388  | 17238  | 11161  |
| ruler-25-7-a3                                                           | t         | 12.4   | 4.1    | 2.1    |
| (sat)                                                                   | n         | 1444   | 255    | 129    |
| frb35-17-2                                                              | t         | 337    | 227    | 194    |
| (sat)                                                                   | n         | 0.13M  | 0.1M   | 78938  |

A likely explanation for the failure of 2-way branching on some instances, compared to its restricted version, is the following. At some right branches during search, the VOH mistakenly chooses to branch on a variable other than the current one. In the case of conflict-driven VOHs, this may result in the search process moving away from a hard subproblem to another area of the search space resulting in increased search effort. To test this conjecture we have developed heuristics, presented below, that can be applied at successful right branches to decide whether the advice of the VOH will be followed or not. The use of such heuristics results in an adaptive branching scheme that dynamically switches between 2-way branching and its restricted version.

Finally, a conclusion that can be drawn from this experimental study is that the performance of different branching schemes strongly depends on the VOH used.

## 4 Heuristics For Adaptive

BRANCHING
We now present two generic heuristics that can be used to dynamically adapt the search algorithm's branching scheme.

We only consider the case where dynamic adaptation involves switching between 2-way branching and restricted 2way branching. As detailed above, the performance of d**-way** branching is very close to that of restricted 2-way branching.

The intuition behind the heuristics is twofold. First, to avoid branching on a different variable if the VOH is not "confident enough" about the correctness of this decision. And second, to identify ways to assist this decision by the use of secondary advisors. That is, VOHs that can complementarily be consulted to help in the decision making.

These heuristics can be applied at successful right branches.

That is, when the VOH suggests to branch on another variable