Solution of Large Dense Transportation Problems Using a Parallel Primal Algorithm
Abstract
A version of the primal transportation code is implemented on a 14 processor BBN Butterfly computer and solved a variety of large, fully dense, randomly generated transportation and assignment problems ranging in sizes up to m = n = 3000. The search phase of primal transportation algorIthm was well suited for implementation on the Butterfly, but the pivot phase could not be parallelized. Computational experience is presented showing that speedup factors for a parallel over a sequential computer of approximately 70 percent of the theoretical maximum were obtained. With the parallel code the empirical difficulty of solving an nxn transportation problem was proportional to n superscript a where a varied between 2.0 and 2.2.Four tables containing the run time information are presented. Additional information concerns the dispersion of run times, build initial tree time, search and pivot time, number of rows searched, number of pivots, and number of pivots per search. This information may be useful to others who are implementing the primal or other transportation algorithms on parallel computers.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1988
- Accession Number
- ADA196238
Entities
People
- Donald L. Miller
- Gerald L. Thompson
- Joseph F. Pekny
Organizations
- Carnegie Mellon University