However, these are some of the most 'extreme' instances. Exponential differences, as predicted between 2-way and d**-way in theory, occured rarely**3.

Table 2. Average speed-up (positive values) or slow-down (negative **values) achieved**
by 2-way branching compared to the other branching methods. **Cpu time (t) in seconds** and visited nodes (n) have been measured.

| %                | d-way         | 2-way                                                  | d-way   | 2-way   |        |        |       |       |
|------------------|---------------|--------------------------------------------------------|---------|---------|--------|--------|-------|-------|
| P roblem         | graph         | d-way dom                                              | ties    | ties    | clust. | clust. |       |       |
| Class            | density       | split. set branch. set branch. set branch. set branch. |         |         |        |        |       |       |
| langf ord        | 1.045         | t                                                      | 2.88    | 5.08    | -1.21  | -1.11  | -1.20 | -1.04 |
| (unsat)          | n -1.27       | 1.52                                                   | -1.26   | -1.06   | -1.23  | -1.03  |       |       |
| pigeons          | 1             | t                                                      | 1.13    | 1.24    | -1.53  | -1.89  | -1.07 | -1.32 |
| (unsat)          | n -1.21       | 1.33                                                   | -1.7    | -1.66   | -1.25  | -1.12  |       |       |
| queensKnights    | 0.70          | t                                                      | 1.49    | 1.99    | 1.75   | -1.21  | -1.02 | -1.48 |
| (unsat)          | n             | 2.85                                                   | 4.96    | 3.47    | 3.04   | 1.87   | 2.39  |       |
| f orced random   | 0.65          | t -1.22                                                | 1.88    | -1.30   | -1.03  | -1.14  | 1.14  |       |
| (sat)            | n -1.41       | 1.52                                                   | -1.11   | -1.1    | -1.24  | 1.07   |       |       |
| geometric        | 0.35          | t -2.48                                                | 2.07    | -4.55   | -1.03  | -3.83  | -2.58 |       |
| (sat)            | n -3.02       | 1.79                                                   | -3.77   | 1.18    | -3.53  | -2.25  |       |       |
| qcp − qwh        | 0.125         | t                                                      | 1.78    | 2.34    | 1.28   | 1.99   | 6.08  | 5.63  |
| (sat)            | n -1.09       | 1.12                                                   | -1.06   | 1.5     | 4.08   | 3.84   |       |       |
| driver           | 0.082         | t                                                      | 1.18    | 1.53    | -1.33  | 1.10   | 1.21  | 1.00  |
| (sat)            | n -1.23 -1.06 | -1.71                                                  | -1.24   | -1.23   | -1.43  |        |       |       |
| rlfap (ScensMod) | 0.052         | t                                                      | 5.39    | 3.07    | 3.52   | 1.07   | 3.70  | 1.26  |
| (mixed)          | n             | 4.63                                                   | 2.73    | 4.28    | 1.77   | 4.94   | 2.1   |       |
| graphColoring    | 0.05          | t -1.50                                                | 1.01    | -1.58   | 1.00   | -1.49  | -1.03 |       |
| (mixed)          | n -1.28       | 1.15                                                   | -1.18   | 1.14    | -1.17  | -0.92  |       |       |

In Tables 2 and 3 we summarize the results of our experimental evaluation.

We use 2-way branching as the standard all other branching methods are compared against. In Table 2 we give the average slow-down (or speed-up) of the methods compared to 2-way for each problem class (the two quasigroup classes qcp and qwh are grouped together). We have mostly selected problem classes that contain either only satisfiable or only unsatisfiable instances. However, we have also experimented with "mixed" problem classes. That is classes that contain both satisfiable and unsatisfiable instances. For example, on langford problems all instances are unsatisfiable and 2-way is 2.88 times better than d**-way**
on average, while it is 1.2 times worse than d**-way clustering set branching. As** mentioned above, it is difficult to accurately compare the numbers of **visited** nodes under different branching schemes. However, in most problem classes the differences in Cpu times roughly reflect the differences in visited nodes.

In Table 3 we give the percentage of instances, over all the tried instances, where each method was faster (> 1), at least 2 times faster (> **2), and at least**