Multi-granularity hybrid parallel network simplex algorithm for minimum-cost flow problems
- PDF / 4,547,622 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 198 Views
Multi‑granularity hybrid parallel network simplex algorithm for minimum‑cost flow problems Jincheng Jiang1 · Jinsong Chen1 · Chisheng Wang2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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 highcomputational 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 highperformance computing platforms. Experimental results demonstrated that MPNSA has very great accelerating effects and the maximum speedup reaches 18.7. Keywords Network simplex algorithm · Minimum-cost flow problem · Multigranularity · Hybrid parallel mode · High-performance computing platform
Electronic supplementary material The online version of this article (https://doi.org/10.1007/s1122 7-020-03227-9) contains supplementary material, which is available to authorized users. * Chisheng Wang [email protected] 1
Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China
2
Shenzhen Key Laboratory of Spatial Smart Sensing and Service, Research Institute for Smart Cities, School of Architecture and Urban Planning, Shenzhen University, Shenzhen 518060, China
13
Vol.:(0123456789)
J. Jiang et al.
1 Introduction The minimum-cost flow (MCF) problem is to flow resources from supply nodes to demand nodes at minimum total cost in a directed network, under the constraints of capacities of the arcs and flow conservation. This problem is of many applications, including information communication [1–3], energy [4], manufacturing [5], retailing [6], and transportation [7]. These considerable practical interests have attracted many researchers to propose numerous algorithms, including some weakly polynomial-time ones and strongly polynomial-time ones [8, 9]. The existing algorithms include cycle-canceling [10, 11], successive shortest paths [12], the primal simplex [13, 14], scaling algorithm [15], and approximation algorithm [16]. The network simplex algorithm (NSA) [13, 17, 18] has become one of the most efficient methods to solve MCF problem, even though MCF and the simplex algorithm were initially developed quite
Data Loading...
