Novel two-stage preflow algorithm for solving the maximum flow problem in a network with circles

Abstract

The presence of circles in the network maximum flow problem increases the complexity of the preflow algorithm. This study proposes a novel two-stage preflow algorithm to address this issue. First, this study proves that at least one zero-flow arc must be present when the flow of the network reaches its maximum value. This result indicates that the maximum flow of the network will remain constant if a zero-flow arc within a circle is removed; therefore, the maximum flow of each network without circles can be calculated. The first stage involves identifying the zero-flow arc in the circle when the network flow reaches its maximum. The second stage aims to remove the zero-flow arc identified and modified in the first stage, thereby producing a new network without circles. The maximum flow of the original looped network can be obtained by solving the maximum flow of the newly generated acyclic network. Finally, an example is provided to demonstrate the validity and feasibility of this algorithm. This algorithm not only improves computational efficiency but also provides new perspectives and tools for solving similar network optimization problems.

Keywords

network with circles / maximum flow / zero-flow arc / two-stage preflow algorithm

References

[1] CAO B, ZHAO J W, GU Y, et al. Security-aware industrial wireless sensor network deployment optimization[J]. IEEE Transactions on Industrial Informatics, 2020, 16(8): 5309-5316.

[2] ZHANG L, FENG D M, WU G. Vehicle dynamic load recognition method based on LSTM network[J]. Journal of Southeast University (Natural Science Edition), 2023, 53(2): 187-192. (in Chinese)

[3] GUPTA S P, PYAKUREL U, DHAMALA T N. Multi-commodity flow problem on lossy network with partial lane reversals[J]. Annals of Operations Research, 2023, 323(1): 45-63.

[4] MIRZAEI M, MIRZAPOUR AL-E-HASHEM S M J, AKBARPOUR SHIRAZI M. A maximum-flow network interdiction problem in an uncertain environment under information asymmetry condition: Application to smuggling goods[J]. Computers & Industrial Engineering, 2021, 162: 107708.

[5] DING J, WEN C Y, LI G Q, et al. Target controllability in multilayer networks via minimum-cost maximum-flow method[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 32(5): 1949-1962.

[6] XIE C Y, DONG L. Graph-enhanced neural interactive collaborative filtering[J]. Journal of Southeast University (English Edition), 2022, 38(2): 110-117.

[7] MEHRYAR M, HAFEZALKOTOB A, AZIZI A, et al. Cooperative reliability allocation in network flow problems considering greenhouse gas emissions: Optical fiber networks structure[J]. Journal of Cleaner Production, 2021, 326: 129315.

[8] SHI M Z, LIN Z D. Effectiveness evaluation of railway traffic safety based on the DEMATEL, AHP, and ANP methods[J]. Journal of Southeast University (English Edition), 2023, 39(2): 133-141.

[9] ALIPOUR H, MUÑOZ M A, SMITH-MILES K. Enhanced instance space analysis for the maximum flow problem[J]. European Journal of Operational Research, 2023, 304(2): 411-428.

[10] FORD L R Jr, FULKERSON D R. A simple algorithm for finding maximal network flows and an application to the Hitchcock problem[J]. Canadian Journal of Mathematics, 1957, 9: 210-218.

[11] AHUJA R K, ORLIN J B. A fast and simple algorithm for the maximum flow problem[J]. Operations Research, 1989, 37(5): 748-759.

[12] HUANG D H. A network reliability algorithm for a stochastic flow network with non-conservation flow[J]. Reliability Engineering & System Safety, 2023, 240: 109584.

[13] KARZANOV A. Determining the maximal flow in a network by the method of preflows[J]. Doklady Mathematics, 1974, 15: 434-437.

[14] KARA G, ÖZTURAN C. Algorithm 1002: Graph coloring based parallel push-relabel algorithm for the maximum flow problem[J]. ACM Transactions on Mathematical Software, 2019, 45(4): 1-28.

[15] DEUTSCH M, DAĞDELEN K, JOHNSON T. An open-source program for efficiently computing ultimate pit limits: MineFlow[J]. Natural Resources Research, 2022, 31(3): 1175-1187.

[16] HOLZHAUSER M, KRUMKE S O, THIELEN C. A network simplex method for the budget-constrained minimum cost flow problem[J]. European Journal of Operational Research, 2017, 259(3): 864-872.

[17] LI X L, WANG Y Q, MA G B, et al. Electric load forecasting based on long-short-term-memory network via simplex optimizer during COVID-19[J]. Energy Reports, 2022, 8: 1-12.

[18] HUANG R, FENG M R, CHEN Z J, et al. Exploring network reliability by predicting link status based on simplex neural network[J]. Displays, 2023, 79: 102457.

[19] APAOLAZA I, VALCARCEL L V, PLANES F J. gMCS: Fast computation of genetic minimal cut sets in large networks[J]. Bioinformatics, 2019, 35(3): 535-537.

[20] MIRASKARSHAHI R, ZABETI H, STEPHEN T, et al. MCS2: Minimal coordinated supports for fast enumeration of minimal cut sets in metabolic networks[J]. Bioinformatics, 2019, 35(14): i615-i623.

[21] MATHEW S, MORDESON J N. Directed fuzzy networks as a model to illicit flows and max flow Min cut theorem[J]. New Mathematics and Natural Computation, 2017, 13(3): 219-229.

[22] ZHU H X, SHEN J, SU Z G, et al. RBF neural network regression model based on fuzzy observations[J]. Journal of Southeast University (English Edition), 2013, 29(4): 400-406.

[23] ZHANG R Q, WEI W. A parallel algorithm for the maximum flow problem[J]. International Core Journal of Engineering, 2019, 5: 61-64.

[24] BERTSIMAS D, STELLATO B. The voice of optimization[J]. Machine Learning, 2021, 110(2): 249-277.

[25] BAYCIK N O. Machine learning based approaches to solve the maximum flow network interdiction problem[J]. Computers & Industrial Engineering, 2022, 167: 107873.

[26] ZHANG L, LU J, LEI D. Vulnerability analysis of bus-metro composite network based on complex network and spatial information embedding[J]. Journal of Southeast University (Natural Science Edition), 2019, 49(4): 773-780. (in Chinese)

[27] WANG J J, CAI Y, FENG Y, et al. Novel grey dynamic trend relational analysis models with different types of accumulation delay effects for time-delay systems[J]. Expert Systems with Applications, 2024, 238: 121661.

[28] WU J S, CHEN N, ZHOU C J, et al. Computing the number of loop-free k-hop paths of networks[J]. IEEE Transactions on Services Computing, 2022, 15(4): 2114-2128.

[29] WILLSON S J. Merging arcs to produce acyclic phylogenetic networks and normal networks[J]. Bulletin of Mathematical Biology, 2022, 84(2): 26.

[30] WU Y, YANG Y L, LIU S Y. The network maximum flow based on the flow matrix[J]. System Engineering, 2007, 25(10): 122-125.

Funding

The National Natural Science Foundation of China(72001107); The National Natural Science Foundation of China(72271120); the Fundamental Research Funds for the Central Universities(NS2024047); the Fundamental Research Funds for the Central Universities(NP2024106); the China Postdoctoral Science Foundation(2020T130297); the China Postdoctoral Science Foundation(2019M660119)