Bl. Hickman et D. Scott, A SUBTREE-PARTITIONING ALGORITHM FOR INDUCING PARALLELISM IN NETWORK SIMPLEX DUAL UPDATES, COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 7(2), 1997, pp. 183-197
Citations number
24
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics
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.