Anomalies in Parallel Branch-and-Bound Algorithms

摘要

Branch-and-bound is a popular algorithm design technique that has been successfully used in the solution of problems that arise in various fields (e.g., combinatorial optimization, artificial intelligence, etc.) The authors briefly describe the branch-and-bound method as used in the solution of combinatorial optimization problems. They consider the effects of parallelizing branch-and-bound algorithms by expanding several live nodes simultaneously. It is shown that it is quite possible for a parallel branch-and-bound algorithm using n sub 2 processors to take more time than using n sub 1 processors even though n sub 1 < n sub 2. Furthermore, it is also possible to achieve speedups that are in excess of the ratio n sub 2/n sub 1. Experimental results with the 0/1 Knapsack and Traveling Salesperson problems are also presented.