Parallel Simplex for Large Pure Network Problems: Computational Testing and Sources of Speedup

Richard S. Barr and Betty L. Hickman
Additional contact information
Richard S. Barr: Southern Methodist University, Dallas, Texas
Betty L. Hickman: University of Nebraska at Omaha, Omaha, Nebraska

Operations Research, 1994, vol. 42, issue 1, 65-80

Abstract: This paper reports on a new parallel implementation of the primal simplex method for minimum cost network flow problems that decomposes both the pivoting and pricing operations. The self-scheduling approach is flexible and efficient; its implementation is close in speed to the best serial code when using one processor, and is capable of substantial speedups as parallel computing units are added. An in-depth computational study of randomly generated transportation and transshipment problems verified the effectiveness of this approach, with results on a 20-processor 80386-based system that are competitive with, and occasionally superior to, massively parallel implementations using tens of thousands of processors. A microanalysis of the code's behavior identified unexpected sources of (the occasionally superlinear) speedup, including the evolutionary topology of the network basis.

Keywords: computers/computer science; software: shared-memory parallel processing software; networks; flow algorithms: primal simplex algorithm for pure networks; programming; large-scale systems: optimization of large time-critical networks (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.1.65 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:1:p:65-80

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().