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

Operations Research · 1994 · Volume 42 · Issue 1

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

Enable JavaScript for citation tools and additional paper interactions.