Multi-granularity hybrid parallel network simplex algorithm for minimum-cost flow problems

摘要

Minimum-cost flow problems widely exist in graph theory, computer science, information science, and transportation science. The network simplex algorithm is a fast and frequently used method for solving minimum-cost flow problems. However, the conventional sequential algorithms cannot satisfy the requirement of high-computational efficiency for large-scale networks. Parallel computing has resulted in numerous significant advances in science and technology over the past decades and is potential to develop an effective means to solve the computational bottleneck problem of large-scale networks. This paper first analyzes the parallelizability of network simplex algorithm and then presents a multi-granularity parallel network simplex algorithm (MPNSA) with fine- and coarse-granularity parallel strategies, which are suitable for shared- and distributed-memory parallel applications, respectively. MPNSA is achieved by message-passing interface, open multiprocessing, and compute unified device architecture, so that it can be compatible with different high-performance computing platforms. Experimental results demonstrated that MPNSA has very great accelerating effects and the maximum speedup reaches 18.7.