A SUBTREE-PARTITIONING ALGORITHM FOR INDUCING PARALLELISM IN NETWORK SIMPLEX DUAL UPDATES

This paper reports on the development of a very efficient method for p artitioning the network simplex basis subtree in which dual values mus t be updated during a pivot. The partitioning procedure may be concurr ently executed by multiple processes. The resulting rapid decompositio n of the subtree allows an arbitrary number of processes to be utilize d in the actual dual update. This approach alleviates a primary limita tion of the most efficient parallel network simplex implementation pub lished to date. The new code performs at least as well as the previous implementation on medium-scale problems and reduces average solution time by over 34% on large-scale problems.