PARALLEL SIMPLEX FOR LARGE PURE NETWORK PROBLEMS - COMPUTATIONAL TESTING AND SOURCES OF SPEEDUP

This paper reports on a new parallel implementation of the primal simp lex 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 be st serial code when using one processor, and is capable of substantial speedups as parallel computing units are added. An in-depth computati onal study of randomly generated transportation and transshipment prob lems verified the effectiveness of this approach, with results on a 20 -processor 80386-based system that are competitive with, and occasiona lly superior to, massively parallel implementations using tens of thou sands of processors. A microanalysis of the code's behavior identified unexpected sources of (the occasionally superlinear) speedup, includi ng the evolutionary topology of the network basis.