Design and Experiment on MPI-Based Parallel Network Simplex Algorithm for Network Minimum-Cost Flow
WU Li-xi · Geography and Geo-Information Science · 2016
Network minimum-cost flow algorithms are usually used to solve optimal flow resource allocation problems.However,the traditional sequential algorithm is not efficient enough to satisfy the requirement of computing performance in large-scale network due to its high time-complexity.With the rapid development of computer technology,parallel computing is becoming an effective way of solving the computational bottleneck.This paper utilizes the relatively low time-complexity network simplex algorithm(NSA)to solve the network minimum-cost flow problem,and designs the parallel computing process of NSA.Analyzing to the parallelizability of NSA,distributed parallel NSA using MPI(Message Passing Interface)technology is designed for high-performance computing platform.The topological structures of three types of classical flow networks are discussed and referred to that of geographical networks.Experimental tests on the three classical flow networks demonstrate that the proposed parallel NSA displays notable acceleration effect,and the maximum speedup reaches 5.4.The proposed parallel NSA provides powerful support for rapid solution of large network resource allocation and decision making on national affairs at regional or national scale.