On the best search strategy in parallel branch-and-bound: Best-first search versus lazy depth-first search

The Best-First Search strategy (BeFS) and the Depth-First Search strategy (DFS) are regarded as the prime strategies when solving combinatorial optimization problems by parallel Branch-and-Bound (B&B) – BeFS because of efficiency with respect to the number of nodes explored, and DFS for reasons of space efficiency. We investigate the efficiency of both strategies experimentally, and two versions of each strategy are tested: In the first, a B&B iteration for a node consists of bounding followed by branching on the node if necessary. For the second, the order is reversed – first branching takes place, and then each child of the node is bounded and possibly fathomed. The first is called lazy, the second eager. The strategies are tested on the Quadratic Assignment Problem and the Job Shop Scheduling Problem. We use parallel codes developed specifically for the solution of the problem in question, and hence containing different heuristic rules and tests to speed up computation. In both cases, we start with an initial solution close to but not equal to the optimal solution. Surprisingly, the BeFS-based strategies turn out to be inferior to the DFS-based strategies, both in terms of running times and in terms of bound calculations performed. Furthermore, when tested in a sequential setting, DFS turns out to be still superior because pruning and evaluation tests are more effective in DFS due to the presence of better incumbents.