Accession Number:

ADA125290

Title:

Anomalies in Parallel Branch-and-Bound Algorithms.

Descriptive Note:

Technical rept.,

Corporate Author:

MINNESOTA UNIV MINNEAPOLIS DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1982-12-01

Pagination or Media Count:

24.0

Abstract:

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.

Subject Categories:

  • Theoretical Mathematics
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE