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

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.