Top

The Journal of Supercomputing

Published in:

04-03-2020

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

Authors: Jincheng Jiang, Jinsong Chen, Chisheng Wang

Published in: The Journal of Supercomputing | Issue 12/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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 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.

previous article An integrated semi-automated framework for domain-based polarity words extraction from an unannotated non-English corpus

next article GPU acceleration of Fitch’s parsimony on protein data: from Kepler to Turing

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Rao L, Liu X, Xie L, Liu W (2010) Minimizing electricity cost: optimization of distributed internet data centers in a multi-electricity-market environment. In: INFOCOM, 2010 Proceedings IEEE. IEEE, pp 1–9

Zhao S, Sun X, Chen J, Duan Z, Zhang Y, Zhang Y (2018) Relational granulation method based on quotient space theory for maximum flow problem. Inf Sci. https://doi.org/10.1016/j.ins.2018.12.009CrossRef

Han S, Peng Z, Wang S (2014) The maximum flow problem of uncertain network. Inf Sci 265:167–175MathSciNetMATHCrossRef

Chiaraviglio L, Mellia M, Neri F (2012) Minimizing ISP network energy cost: formulation and solutions. IEEE/ACM Trans Netw 20(2):463–476CrossRef

Basten RJI, Van der Heijden MC, Schutten JMJ (2011) Practical extensions to a minimum cost flow model for level of repair analysis. Eur J Oper Res 211(2):333–342MathSciNetCrossRef

Jin M, Granda-Marulanda NA, Down I (2014) The impact of carbon policies on supply chain design and logistics of a major retailer. J Clean Prod 85:453–461CrossRef

Xie F, Jia Y, Jia R (2012) Algorithm for minimum cost maximum flow in transportation network. J Converg Inf Technol 7(7):165–173

Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms and applications. Prentice-Hall, Englewood CliffsMATH

Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems. J ACM 19(2):248–264MATHCrossRef

10.

Goldberg AV, Tarjan RE (1989) Finding minimum-cost circulations by canceling negative cycles. J ACM 36(4):873–886MathSciNetMATHCrossRef

11.

Sokkalingam PT, Ahuja RK, Orlin JB (2000) New polynomial time cycle-canceling algorithms for minimum-cost flows. Networks 36:53–63MathSciNetMATHCrossRef

12.

Goldberg A, Tarjan R (1987) Solving minimum cost flow problem by successive approximation. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. ACM, pp 7–18

13.

Orlin JB (1997) A polynomial time primal network simplex algorithm for minimum cost flows. Math Program 78(2):109–129MathSciNetMATHCrossRef

14.

Goldfarb D, Hao JX (1990) A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n²m) time. Math Program 47(1–3):353–365MATHCrossRef

15.

Ciupala L (2006) A deficit scaling algorithm for the minimum flow problem. Sadhana 31(3):227–233MathSciNetCrossRef

16.

Holzhauser M, Krumke SO, Thielen C (2016) On the complexity and approximability of budget-constrained minimum cost flows. arXiv preprint arXiv:1607.02282

17.

Armstrong RD, Jin ZY (1997) A new strongly polynomial dual network simplex algorithm. Math Program 78(2):131–148MathSciNetMATHCrossRef

18.

Eusebio A, Figueira JR, Ehrgott M (2009) A primal-dual simplex algorithm for bi-objective network flow problems. 4OR 7(3):255–273MathSciNetMATHCrossRef

19.

Caliskan C (2008) A double scaling algorithm for the constrained maximum flow problem. Comput Oper Res 35(4):1138–1150MathSciNetMATHCrossRef

20.

Holzhauser M, Krumke SO, Thielen C (2017) A network simplex method for the budget-constrained minimum cost flow problem. Eur J Oper Res 259(3):864–872MathSciNetMATHCrossRef

21.

Çalışkan C (2011) A specialized network simplex algorithm for the constrained maximum flow problem. Eur J Oper Res 210(2):137–147MathSciNetMATHCrossRef

22.

Hwu WM (2014) What is ahead for parallel computing. J Parallel Distrib Comput 74(7):2574–2581CrossRef

23.

Sato M (2002) OpenMP: parallel programming API for shared memory multiprocessors and on-chip multiprocessors. In: Proceedings of the 15th International Symposium on System Synthesis. ACM, pp 109–111

24.

Kirk D (2007) NVIDIA CUDA software and GPU parallel computing architecture. In: ISMM, vol 7, pp 103–104

25.

Buck I (2007) GPU computing: programming a massively parallel processor. In: 2007. CGO’07. International Symposium on Code Generation and Optimization. IEEE, p 17

26.

Tziritas N, Khan SU, Xu CZ, Hong J (2012) An optimal fully distributed algorithm to minimize the resource consumption of cloud applications. In: 2012 IEEE 18th International Conference on Parallel and Distributed Systems (ICPADS). IEEE, pp 61–68

27.

Tziritas N, Khan SU, Xu CZ, Loukopoulos T, Lalis S (2013) On minimizing the resource consumption of cloud applications using process migrations. J Parallel Distrib Comput 73(12):1690–1704CrossRef

28.

Bertsekas DP, Castanon DA (1993) Parallel primal–dual methods for the minimum cost flow problem. Comput Optim Appl 2(4):317–336MathSciNetMATHCrossRef

29.

Beraldi P, Guerriero F (1997) A parallel asynchronous implementation of the ε-relaxation method for the linear minimum cost flow problem. Parallel Comput 23(8):1021–1044MathSciNetMATHCrossRef

30.

Beraldi P, Guerriero F, Musmanno R (1997) Efficient parallel algorithms for the minimum cost flow problem. J Optim Theory Appl 95(3):501–530MathSciNetMATHCrossRef

31.

Beraldi P, Guerriero F, Musmanno R (2001) Parallel algorithms for solving the convex minimum cost flow problem. Comput Optim Appl 18(2):175–190MathSciNetMATHCrossRef

32.

Imai H, Iwano K (1990) Efficient sequential and parallel algorithms for planar minimum cost flow. In: Asano T, Ibaraki T, Imai H, Nishizeki T (eds) Algorithms. SIGAL 1990. Lecture Notes in Computer Science, vol 450. Springer, Berlin, Heidelberg, pp 21–30

33.

Orlin JB, Stein C (1993) Parallel algorithms for the assignment and minimum-cost flow problems. Oper Res Lett 4(14):181–186MathSciNetMATHCrossRef

34.

Andrzej L, Mia P (2012) A fast parallel algorithm for minimum-cost small integral flows. In: Euro-Par 2012 Parallel Processing. Springer, Berlin, pp 688–699

35.

Lingas A, Persson M (2015) A fast parallel algorithm for minimum-cost small integral flows. Algorithmica 72(2):607–619MathSciNetMATHCrossRef

36.

Yarmish G, Slyke R (2009) A distributed, scaleable simplex method. J Supercomput 49(3):373–381CrossRef

37.

Ploskas N, Samaras N, Margaritis K (2013) A parallel implementation of the revised simplex algorithm using OpenMP: some preliminary results. In: Optimization Theory, Decision Making, and Operational Research Applications, Springer Proceedings in Mathematics and Statistics, vol 31, pp 163–175

38.

Lalami ME, Boyer V, El-Baz D (2011) Efficient implementation of the simplex method on a CPU–GPU system. In: Proceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, Washington DC, 16–20 May 2011, pp 1999–2006

39.

Bieling J, Peschlow P, Martini P (2010) An efficient GPU implementation of the revised simplex method. In: Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium, 19–23 April 2010, Atlanta, pp 1–8

40.

Meyer X, Albuquerque P, Chopard B (2011) A MultiGPU implementation and performance model for the standard simplex method. In: Proceedings of the 1st International Symposium and 10th Balkan Conference on Operational Research, 22–25 September 2011, Thessaloniki, pp 312–319

41.

Tar P, Stágel B, Maros I (2017) Parallel search paths for the simplex algorithm. CEJOR 25(4):967–984MathSciNetMATHCrossRef

42.

Hall JAJ, McKinnon KIM (1998) ASYNPLEX, an asynchronous parallel revised simplex algorithms. Ann Oper Res 81:27–50MathSciNetMATHCrossRef

43.

Klabjan D, Johnson EL, Nemhauser GL (2000) A parallel primal–dual simplex algorithm. Oper Res Lett 27(2):47–55MathSciNetMATHCrossRef

44.

Lubin M, Hall JAJ, Petra CG, Anitescu M (2013) Parallel distributed-memory simplex for large-scale stochastic LP problems. Comput Optim Appl 55(3):571–596MathSciNetMATHCrossRef

45.

Thulasiraman K, Chalasani RP, Comeau MA (1993) Parallel network dual simplex method on a shared memory multiprocessor. In: Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing, 1993. IEEE, pp 408–415

46.

Mamalis B, Perlitis M (2016) A hybrid parallelization scheme for standard simplex method based on CPU/GPU collaboration. In: Proceedings of the 20th Pan-Hellenic Conference on Informatics, pp 1–6

47.

Huangfu Q, Hall JJ (2018) Parallelizing the dual revised simplex method. Math Program Comput 10(1):119–142MathSciNetMATHCrossRef

48.

Zhong Z, Feng M, Liu D (2015) Parallelization of revised simplex algorithm on GPUs. In: 2015 International Conference on Network and Information Systems for Computers. IEEE, pp 349–353

49.

He L, Bai H, Jiang Y, Ouyang D, Jiang S (2018) Revised simplex algorithm for linear programming on GPUs with CUDA. Multimed Tools Appl 77(22):30035–30050CrossRef

50.

Goldberg AV, Tarjan RE (1988) A new approach to the maximum flow problem. J ACM 35(4):921–940MathSciNetMATHCrossRef

51.

Harel D, Tarjan RE (1984) Fast algorithms for finding nearest common ancestors. SIAM J Comput 13(2):338–355MathSciNetMATHCrossRef

52.

Eppstein D (1994) Clustering for faster network simplex pivots. In: SODA, pp 160–166

53.

Ahuja RK, Orlin JB (1996) Use of representative operation counts in computational testing of algorithms. Informs J Comput 8(3):318–330MATHCrossRef

54.

Ahuja RK, Orlin JB, Sharma P, Sokkalingam PT (2002) A network simplex algorithm with O(n) consecutive degenerate pivots. Oper Res Lett 30(3):141–148MathSciNetMATHCrossRef

55.

Cormen TH et al (2001) Introduction to algorithms. MIT Press, CambridgeMATH

56.

Kelly DJ, ONeill GM (1991) The minimum cost flow problem and the network simplex solution method. Doctoral dissertation, University College Dublin, Graduate School of Business

57.

Badics T, Boros E, Cepek O (1993) Implementing a new maximum flow algorithm. In: Johnson DS, McGeoch CC (eds) Network flows and matching: first DIMACS implementation challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol 12. American Mathematical Society, Providence

Title: Multi-granularity hybrid parallel network simplex algorithm for minimum-cost flow problems
Authors: Jincheng Jiang
Jinsong Chen
Chisheng Wang
Publication date: 04-03-2020
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 12/2020
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-020-03227-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 12/2020

Dynamic clustering method for imbalanced learning based on AdaBoost

Image-based stroke rat brain atrophy volume and infarct volume computation

An enhanced rerouting cost estimation algorithm towards internet of drone

EAAM: Energy-aware application management strategy for FPGA-based IoT-Cloud environments

A novel method for victim block selection for NAND flash-based solid state drives based on scoring

A survey on security challenges in cloud computing: issues, threats, and solutions

Premium Partner