Anomalies in Parallel Branch-and-Bound Algorithms.
MINNESOTA UNIV MINNEAPOLIS DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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 2n sub 1. Experimental results with the 01 Knapsack and Traveling Salesperson problems are also presented.
- Theoretical Mathematics
- Computer Hardware