Generalized Networks: Parallel Algorithms and an Empirical Analysis
File(s)
Date
1989Author
Clark, Robert H
Kennington, JL
Meyer, Robert R
Ramamurti, M
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
The objective of this research was to develop and empirically test simplex ?based parallel algorithms for the generalized network optimization problem. Several parallel algorithms were developed that utilize the multitasking capabilities of the Sequent Symmetry S81 multiprocessor. The software implementations of these parallel algorithms were empirically tested on a variety of problems produced by two random problem generators and compared with two leading state-of-the-art serial codes. Speedups on fifteen processors ranged from 2.6 to 5.9 for a test set of fifteen randomly generated transshipment problems. A group of six generalized transportation problems yielded speedups of up to 11 using nineteen processors. An enormous generalized transportation problem having 30,000 nodes and 1.2 million arcs was optimized in approximately ten minutes by our parallel code. A speedup of 13 was achieved on this problem using 15 processors.
Permanent Link
http://digital.library.wisc.edu/1793/59238Citation
TR904