Rs. Barr et Bl. Hickman, PARALLEL SIMPLEX FOR LARGE PURE NETWORK PROBLEMS - COMPUTATIONAL TESTING AND SOURCES OF SPEEDUP, Operations research, 42(1), 1994, pp. 65-80
Citations number
28
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
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.