A Parallel Shortest Augmenting Path Algorithm for the Assignment Problem

Abstract

We describe a parallel version of the shortest augmenting path algorithm for the assignment problem. While generating the initial dual solution and partial assignment in parallel does not require substantive changes in the sequential algorithm, using several augmenting paths in parallel does require a new dual variable recalculation method. The parallel algorithm was tested on a 14-processor Butterfly Plus computer, on problems with up to 900 million variables. The speedup obtained increases with problem size. The algorithm was also embedded into a parallel branch and bound procedure for the traveling salesman problem on a directed graph, which was test on the Butterfly Plus on problems involving up to 7,500 cities. To our knowledge, these are the largest assignment problems and traveling salesman problems solved so far.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1989
Accession Number
ADA233588

Entities

People

  • Donald Miller
  • Egon Balas
  • Joseph Pekny
  • Paolo Toth

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Access Time
  • Algorithms
  • Computations
  • Computer Programming
  • Computers
  • Data Transmission
  • Efficiency
  • Integer Programming
  • Lepidoptera
  • Linear Programming
  • Military Research
  • Parallel Computing
  • Programming Languages
  • Simplex Method
  • Sparse Matrix
  • Trees (Data Structures)

Readers

  • Operations Research
  • Parallel and Distributed Computing.