Anomalies in Parallel Branch-and-Bound Algorithms.

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 2/n sub 1. Experimental results with the 0/1 Knapsack and Traveling Salesperson problems are also presented.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1982
Accession Number
ADA125290

Entities

People

  • Sartaj Sahni
  • Ten-hwang Lai

Organizations

  • University of Minnesota

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computer Science
  • Computers
  • Degradation
  • Iterations
  • Military Research
  • Minnesota
  • New York
  • Optimization
  • Parallel Computing
  • Parallel Processing
  • Sequences
  • Simulations
  • Standards
  • Trees (Data Structures)

Readers

  • Operations Research
  • Parallel and Distributed Computing.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms