
| Max Nodes   | Solved Instances   | Combination of Heuristics                    |
|-------------|--------------------|----------------------------------------------|
| 100         | 516                | H                                            |
| 200         | 705                | H                                            |
| 300         | 759                | H 8 -s-g, H 8 -d-l                           |
| 400         | 769                | H 8 -s-g, C 8 -d-l                           |
| 500         | 74                 | Hs-s-g, Hs-d-l, Cs-d-l                       |
| 600         | 778                | H 8 -s-g, H 8 -d-l, C 8 -d-l, B -s-l         |
| 700         | 780                | H 8 -s-g, H 8 -d-l, C 8 -d-l, B -s-l         |
| 800         | 783                | H 8 -s-g, H 8 -d-l, C 8 -d-l, B -s-l         |
| 900         | 784                | H 8 -s-g, H 8 -d-l, C 8 -d-l, B -s-l         |
| 1100        | 785                | H 8 -s-g, H 8 -d-l, C 8 -d-l, B -s-l, B -s-g |
| 1 300       | 786                | H 8 -s-g, H 8 -d-l, B -s-l, B -s-g           |
| 3900        | 787                | Hs-s-g, Hs-d-l, B-d-l                        |

Table 3: Best performance of combining different heuristics for solving the 787 solvable hard instances of A(n,d, 4.0) with a fixed maximal number of visited nodes

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

d = 2.0 to d = 18.0 with a step of 0.5, a total number of 132,000 instances. Since solving large instances using backtracking requires a lot of memory, we solved the instances on a Sun Ultra60 with 1GB of main memory.

The generated instances display a phase-transition behavior which continues the one given in Figure 5.  The phase-transition ranges from d = 10.0 for n = 110 to d = 10.5 for n = 500 (see Figure 13). Apart from 112 instances, all other instances we generated were solvable by orthogonal combination of the four heuristics ( H s/static/global, H s /dynamic/local, C s /dynamic/local, B /static/local ) spending less than 2n visited nodes