The Maximum Attainable Flow and Minimal Cost Problem in a Network

Amanuel Belachew Beyi; Temesgen Alemu Godana

doi:doi:10.11648/j.ajmcm.20240902.11

Review Article |

| Peer-Reviewed

The Maximum Attainable Flow and Minimal Cost Problem in a Network

Amanuel Belachew Beyi, Temesgen Alemu Godana^*

Published in American Journal of Mathematical and Computer Modelling (Volume 9, Issue 2)

Received: 31 March 2024 Accepted: 6 May 2024 Published: 17 May 2024

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

This paper, presents an efficient algorithm that solves such a large class of optimization problems. Ford-Fulkerson determines the maximum flow in a network by iteratively augmenting flow paths until no further improvement is possible. On the other hand, Dijkstra's algorithm excels in finding the shortest path in a weighted graph, making it suitable for minimizing costs in network traversal. However, this paper simultaneously optimizes both objectives (flow and cost) dependently in unique iterations by considering all constraints and objectives holistically. The aim of this work is to develop efficient algorithms that can handle complex optimization problems in transportation, network design, and other fields, ultimately improving resource utilization and minimizing costs as its crucial for enhancing decision-making processes, improving efficiency in resource utilization, and achieving cost savings in diverse applications ranging from transportation networks to production planning. This paper deals about formulating the linear programming for the optimizations problems and finding the maximum amount of flow that can be sent from a source node to a sink node while minimizing the total cost of sending that flow by using simplex method (Two phase method). Through computational experiments and case studies, everybody demonstrate the effectiveness and efficiency of the proposed approach in solving real-world network flow problems. Our method yields efficient algorithms with in smallest numbers of iterations and time that enable the optimal allocation of resources within networks, achieving both maximum flow and minimum cost simultaneously.

Published in	American Journal of Mathematical and Computer Modelling (Volume 9, Issue 2)
DOI	10.11648/j.ajmcm.20240902.11
Page(s)	22-37
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Maximum Flow, Minimum Cost, Linear Programming, Network Flow Optimization, Two Phase Method

References

[1]	Bazaraa, M. S., Jarvis, J. J., and Sherali, H. D., Linear Programming and Network Flows, 4th Ed., John Wiley and Sons, Inc, 2019.
[2]	Christiano, P., Kelner, J. A., Madry, A., Spielman, D. A., and Teng, S-H. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the Annual ACM Symposium on Theory of Computing. ACM Press, New York, 2021, 273–282.
[3]	Dinic, E. A. Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Mathematical Docladi 11 (2022), 1277–1280.
[4]	Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., Upper Saddle River, NJ, 1993.
[5]	Goldberg, A. V., Hed, S., Kaplan, H., Tarjan, R. E., and Werneck, R. F. Maximum flows by incremental breadth-first search. In Proceedings of the 19th European Symposium on Algorithms. Springer-Verlag, Heidelberg, Germany, 2011, 457–468.
[6]	E. L. Lawler, Combinatorial optimization: Networks and matroids (Holt, Rinehart & Winston, NewYork, 2022).
[7]	J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19: 248 264, 2018.
[8]	Hu, T. C.: Integer Programming and Network Flows. Addison-Wesley Publishing Company, Ontario (1970).
[9]	Baloukas, Th., Paparrizos, K., and Sifaleras, A., “An Animated Demonstration of the Uncapacitated Network Simplex Algorithm”, INFORMS Transactions on Education, 10 (1) (2019) 34–40.
[10]	Andreou, D., Paparrizos, K., Samaras, N., and Sifaleras, A., “Application of a new network – enabled solver for the assignment problem in computer – aided education”, Journal of Computer Science, 1 (1) (2020) 19–23.
[11]	Boykov, Y. and Kolmogorov, V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 9 (2023), 1124–1137.
[12]	Goldberg, A. V. and Tarjan, R. E. A new approach to the maximum flow problem. Journal of the ACM 35, 4 (2019), 921–940.
[13]	D. R. Fulkerson. An out-of-kilter method for minimal cost flow problems. SIAM Journal, 1961.
[14]	Babenko, M. A., Derryberry, J., Goldberg, A. V., Tarjan, R. E., and Zhou, Y. Experimental evaluation of parametric max-flow algorithms. In Proceedings of the Sixth Workshop on Experimental Algorithms, Lecture Notes in Computer Science. Springer, Heidelberg, Germany, 2007, 256–269.
[15]	Ford, L. R., Fulkerson, D. R.: Flows in Networks. Princeton University Press, Princeton (1962).
[16]	Alan Gibbons, Algorithmic Graph Theory in Network Application, Cambridge University Press, 1985.
[17]	Minieka, E.: Optimization Algorithms for Networks and Graphs. Marcel Dekker, Inc., New York and Basel (2018).
[18]	Andreou, D., Paparrizos, K., Samaras, N., and Sifaleras, A., “Visualization of the network exterior primal simplex algorithm for the minimum cost network flow problem”, Operational Research, 7 (3) (2007) 449–464.
[19]	Borradaile, G. and Klein, P. N. An O (n log n) algorithm for maximum st-flow in a directed planar graph. Journal of the ACM 56, 2 (2021), 1–34.
[20]	Basten, R. J. I., Heijden, M. C., and Schutten, J. M. J., “A minimum cost flow model for level of repair analysis”, International Journal of Production Economics, 133(1) (2022) 233–242.
[21]	Beraldi, P., Guerriero, F., and Musmanno, R., “Parallel Algorithms for Solving the Convex Minimum Cost Flow Problem”, Computational Optimization and Applications, 18 (2) (2021) 175–190.
[22]	Cherkassky, B. V. and Goldberg, A. V. On implementing push-relabel method for the maximum flow problem. Algorithmica 19, 4 (1997), 390–410.
[23]	Dantzig, G. B. Application of the simplex method to a transportation problem. In Activity Analysis and Production and Allocation, T. C. Koopmans, Ed. John Wiley & Sons, Inc., New York, 1951, 359–373.
[24]	Ford, Jr., L. R. and Fulkerson, D. R. Maximal flow through a network. Canadian Journal of Mathematics 8 (1956), 399–404.
[25]	Kelner, A., Lee, Y. T., Orecchia, L., and Sidford, A. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, 2023, 217–226.

Cite This Article

Plain Text BibTeX RIS

APA Style

Beyi, A. B., Godana, T. A. (2024). The Maximum Attainable Flow and Minimal Cost Problem in a Network. American Journal of Mathematical and Computer Modelling, 9(2), 22-37. https://doi.org/10.11648/j.ajmcm.20240902.11

Copy | Download

ACS Style

Beyi, A. B.; Godana, T. A. The Maximum Attainable Flow and Minimal Cost Problem in a Network. Am. J. Math. Comput. Model. 2024, 9(2), 22-37. doi: 10.11648/j.ajmcm.20240902.11

Copy | Download

AMA Style

Beyi AB, Godana TA. The Maximum Attainable Flow and Minimal Cost Problem in a Network. Am J Math Comput Model. 2024;9(2):22-37. doi: 10.11648/j.ajmcm.20240902.11

Copy | Download

@article{10.11648/j.ajmcm.20240902.11,
  author = {Amanuel Belachew Beyi and Temesgen Alemu Godana},
  title = {The Maximum Attainable Flow and Minimal Cost Problem in a Network
},
  journal = {American Journal of Mathematical and Computer Modelling},
  volume = {9},
  number = {2},
  pages = {22-37},
  doi = {10.11648/j.ajmcm.20240902.11},
  url = {https://doi.org/10.11648/j.ajmcm.20240902.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmcm.20240902.11},
  abstract = {This paper, presents an efficient algorithm that solves such a large class of optimization problems. Ford-Fulkerson determines the maximum flow in a network by iteratively augmenting flow paths until no further improvement is possible. On the other hand, Dijkstra's algorithm excels in finding the shortest path in a weighted graph, making it suitable for minimizing costs in network traversal. However, this paper simultaneously optimizes both objectives (flow and cost) dependently in unique iterations by considering all constraints and objectives holistically. The aim of this work is to develop efficient algorithms that can handle complex optimization problems in transportation, network design, and other fields, ultimately improving resource utilization and minimizing costs as its crucial for enhancing decision-making processes, improving efficiency in resource utilization, and achieving cost savings in diverse applications ranging from transportation networks to production planning. This paper deals about formulating the linear programming for the optimizations problems and finding the maximum amount of flow that can be sent from a source node to a sink node while minimizing the total cost of sending that flow by using simplex method (Two phase method). Through computational experiments and case studies, everybody demonstrate the effectiveness and efficiency of the proposed approach in solving real-world network flow problems. Our method yields efficient algorithms with in smallest numbers of iterations and time that enable the optimal allocation of resources within networks, achieving both maximum flow and minimum cost simultaneously.
},
 year = {2024}
}

Copy | Download

TY  - JOUR
T1  - The Maximum Attainable Flow and Minimal Cost Problem in a Network

AU  - Amanuel Belachew Beyi
AU  - Temesgen Alemu Godana
Y1  - 2024/05/17
PY  - 2024
N1  - https://doi.org/10.11648/j.ajmcm.20240902.11
DO  - 10.11648/j.ajmcm.20240902.11
T2  - American Journal of Mathematical and Computer Modelling
JF  - American Journal of Mathematical and Computer Modelling
JO  - American Journal of Mathematical and Computer Modelling
SP  - 22
EP  - 37
PB  - Science Publishing Group
SN  - 2578-8280
UR  - https://doi.org/10.11648/j.ajmcm.20240902.11
AB  - This paper, presents an efficient algorithm that solves such a large class of optimization problems. Ford-Fulkerson determines the maximum flow in a network by iteratively augmenting flow paths until no further improvement is possible. On the other hand, Dijkstra's algorithm excels in finding the shortest path in a weighted graph, making it suitable for minimizing costs in network traversal. However, this paper simultaneously optimizes both objectives (flow and cost) dependently in unique iterations by considering all constraints and objectives holistically. The aim of this work is to develop efficient algorithms that can handle complex optimization problems in transportation, network design, and other fields, ultimately improving resource utilization and minimizing costs as its crucial for enhancing decision-making processes, improving efficiency in resource utilization, and achieving cost savings in diverse applications ranging from transportation networks to production planning. This paper deals about formulating the linear programming for the optimizations problems and finding the maximum amount of flow that can be sent from a source node to a sink node while minimizing the total cost of sending that flow by using simplex method (Two phase method). Through computational experiments and case studies, everybody demonstrate the effectiveness and efficiency of the proposed approach in solving real-world network flow problems. Our method yields efficient algorithms with in smallest numbers of iterations and time that enable the optimal allocation of resources within networks, achieving both maximum flow and minimum cost simultaneously.

VL  - 9
IS  - 2
ER  -

Copy | Download

Author Information

Amanuel Belachew Beyi

College of Natural & Computational Science, Addis Ababa University, Addis Ababa, Ethiopia

Contact Email
Temesgen Alemu Godana

College of Natural & Computational Science, Addis Ababa University, Addis Ababa, Ethiopia

Contact Email

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Beyi, A. B., Godana, T. A. (2024). The Maximum Attainable Flow and Minimal Cost Problem in a Network. American Journal of Mathematical and Computer Modelling, 9(2), 22-37. https://doi.org/10.11648/j.ajmcm.20240902.11

Copy | Download

ACS Style

Beyi, A. B.; Godana, T. A. The Maximum Attainable Flow and Minimal Cost Problem in a Network. Am. J. Math. Comput. Model. 2024, 9(2), 22-37. doi: 10.11648/j.ajmcm.20240902.11

Copy | Download

AMA Style

Beyi AB, Godana TA. The Maximum Attainable Flow and Minimal Cost Problem in a Network. Am J Math Comput Model. 2024;9(2):22-37. doi: 10.11648/j.ajmcm.20240902.11

Copy | Download

@article{10.11648/j.ajmcm.20240902.11,
  author = {Amanuel Belachew Beyi and Temesgen Alemu Godana},
  title = {The Maximum Attainable Flow and Minimal Cost Problem in a Network
},
  journal = {American Journal of Mathematical and Computer Modelling},
  volume = {9},
  number = {2},
  pages = {22-37},
  doi = {10.11648/j.ajmcm.20240902.11},
  url = {https://doi.org/10.11648/j.ajmcm.20240902.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmcm.20240902.11},
  abstract = {This paper, presents an efficient algorithm that solves such a large class of optimization problems. Ford-Fulkerson determines the maximum flow in a network by iteratively augmenting flow paths until no further improvement is possible. On the other hand, Dijkstra's algorithm excels in finding the shortest path in a weighted graph, making it suitable for minimizing costs in network traversal. However, this paper simultaneously optimizes both objectives (flow and cost) dependently in unique iterations by considering all constraints and objectives holistically. The aim of this work is to develop efficient algorithms that can handle complex optimization problems in transportation, network design, and other fields, ultimately improving resource utilization and minimizing costs as its crucial for enhancing decision-making processes, improving efficiency in resource utilization, and achieving cost savings in diverse applications ranging from transportation networks to production planning. This paper deals about formulating the linear programming for the optimizations problems and finding the maximum amount of flow that can be sent from a source node to a sink node while minimizing the total cost of sending that flow by using simplex method (Two phase method). Through computational experiments and case studies, everybody demonstrate the effectiveness and efficiency of the proposed approach in solving real-world network flow problems. Our method yields efficient algorithms with in smallest numbers of iterations and time that enable the optimal allocation of resources within networks, achieving both maximum flow and minimum cost simultaneously.
},
 year = {2024}
}

Copy | Download

TY  - JOUR
T1  - The Maximum Attainable Flow and Minimal Cost Problem in a Network

AU  - Amanuel Belachew Beyi
AU  - Temesgen Alemu Godana
Y1  - 2024/05/17
PY  - 2024
N1  - https://doi.org/10.11648/j.ajmcm.20240902.11
DO  - 10.11648/j.ajmcm.20240902.11
T2  - American Journal of Mathematical and Computer Modelling
JF  - American Journal of Mathematical and Computer Modelling
JO  - American Journal of Mathematical and Computer Modelling
SP  - 22
EP  - 37
PB  - Science Publishing Group
SN  - 2578-8280
UR  - https://doi.org/10.11648/j.ajmcm.20240902.11
AB  - This paper, presents an efficient algorithm that solves such a large class of optimization problems. Ford-Fulkerson determines the maximum flow in a network by iteratively augmenting flow paths until no further improvement is possible. On the other hand, Dijkstra's algorithm excels in finding the shortest path in a weighted graph, making it suitable for minimizing costs in network traversal. However, this paper simultaneously optimizes both objectives (flow and cost) dependently in unique iterations by considering all constraints and objectives holistically. The aim of this work is to develop efficient algorithms that can handle complex optimization problems in transportation, network design, and other fields, ultimately improving resource utilization and minimizing costs as its crucial for enhancing decision-making processes, improving efficiency in resource utilization, and achieving cost savings in diverse applications ranging from transportation networks to production planning. This paper deals about formulating the linear programming for the optimizations problems and finding the maximum amount of flow that can be sent from a source node to a sink node while minimizing the total cost of sending that flow by using simplex method (Two phase method). Through computational experiments and case studies, everybody demonstrate the effectiveness and efficiency of the proposed approach in solving real-world network flow problems. Our method yields efficient algorithms with in smallest numbers of iterations and time that enable the optimal allocation of resources within networks, achieving both maximum flow and minimum cost simultaneously.

VL  - 9
IS  - 2
ER  -

Copy | Download