Generalized Networks: Parallel Algorithms and an Empirical Analysis

Abstract

The objective of this research was to develop and empirically test simplex ?based parallel algorithms for the generalized network optimization problem. Several parallel algorithms were developed that utilize the multitasking capabilities of the Sequent Symmetry S81 multiprocessor. The software implementations of these parallel algorithms were empirically tested on a variety of problems produced by two random problem generators and compared with two leading state-of-the-art serial codes. Speedups on fifteen processors ranged from 2.6 to 5.9 for a test set of fifteen randomly generated transshipment problems. A group of six generalized transportation problems yielded speedups of up to 11 using nineteen processors. An enormous generalized transportation problem having 30,000 nodes and 1.2 million arcs was optimized in approximately ten minutes by our parallel code. A speedup of 13 was achieved on this problem using 15 processors.