The Maximum Flow and Minimum Cost–Maximum Flow Problems: Computing and Applications
Asian Journal of Probability and Statistics,
Page 2857
DOI:
10.9734/ajpas/2020/v7i330185
Abstract
The maximum flow and minimum costmaximum flow problems are both concerned with determining flows through a network between a source and a destination. Both these problems can be formulated as linear programming problems. When given information about a network (network flow diagram, capacities, costs), computing enables one to arrive at a solution to the problem. Once the solution becomes available, it has to be applied to a real world problem. The use of the following computer software in solving these problems will be discussed: R (several packages and functions), specially written Pascal programs and Excel SOLVER. The minimum costmaximum flow solutions to the following problems will also be discussed: maximum flow, minimum costmaximum flow, transportation problem, assignment problem, shortest path problem, caterer problem.
Keywords:
 Maximum flow
 minimum costmaximum flow
 nodes
 arcs
 source
 sink
 capacities
 costs
 objective function
 flow conservation and capacity constraints
 algorithm
 optimal solution
 network optimization
 transportation problem
 assignment problem
 shortest path problem
 caterer problem.
How to Cite
References
Kaanodiya KK, Rizwanullah M. Minimize traffic congestion: An application of maximum flow in dynamic networks. Journal of Applied Mathematics, Statistics and Informatics (JAMSI). 2012;8(1): 6374.
Schwartz BL. Possible winners in partially completed tournaments. SIAM Review. 1966;8(3):302308.
DOI: 10.1137/1008062
Winston WL. Operations research applications and algorithms. 4th Ed. Belmont CA, USA, Brooks/ColeThomson Learning; 2004.
Dantzig GB. Linear programming and extensions. Princeton University Press, Princeton, NJ; 1963.
Kuhn HW. The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 1955; 2(12):8397.
Available:CiteSeerX10.1.1.228.3906
DOI: 10.1002/nav.3800020109
Lone MA, Mir SA, Wani MS. An application of assignment problem in agriculture using R. Journal of Scientific Research & Reports. 2017;13(2):15.
Hultberg TH, Cardoso DM. The teacher assignment problem: A special case of the fixed charge transportation problem. European Journal of Operation Research. 1997;101:463473.
Feiyang Chen, Nan Chen, Hanyang Mao, Hanlin Hu. An application of bipartite matching in assignment problem. Chuangxinban Journal of Computing. 2018;12.
Available:https://arxiv.org/pdf/1902.00256.pdf
Demaine E, Goldwasser S. Introduction to algorithms. Massachusetts Institute of Technology Hand Out 25; 2004.
Szwarc W, Posner ME. The caterer problem. Operations Research. 1985;33(6):12151224.
Ahuja RK, Magnanti TL, Orlin JB, Reddy MR. Applications of network optimization. Chapter in Handbooks in OR & MS, Elsevier. 1995;7.
Harris TE, Ross FS. Fundamentals of a method for evaluating rail net capacities. Research Memorandum, Rand Corporation; 1955.
Ford LR, Fulkerson DR. Maximal flow through a network. Canadian Journal of Mathematics. 1956;8:399404.
Dinitz Y. Algorithm for solution of a problem of maximum flow in a network with power estimation. Doklady Akademii Nauk SSSR. 1970;11:12771280.
Edmonds J, Karp JM. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM. 1972;19(2):248264.
Goldberg AV, Tarjan RE. A new approach to the maximum flow problem. Journal of the ACM. 1988;35(4):921940.
Goldberg AV, Rao S. Beyond the flow decomposition barrier. Journal of the ACM. 1998;45(5):783797.
King V, Rao S, Tarjan R. A faster deterministic maximal flow algorithm. Journal of Algorithms. 1994;17:447474.
Orlin JB. Max flows in O(nm) time, or better. STOC '13 Proceedings of the Fortyfifth Annual ACM Symposium on Theory of Computing. 2013;765–774.
Available:CiteSeerX10.1.1.259.5759
DOI: 10.1145/2488608.2488705
ISBN: 9781450320290
Sherman J. Nearly maximum flows in nearly linear time. Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science. 2013;263269.
Malhotra VM, PramodhKumar SN, Maheshwari SN. An algorithm for finding maximum flows in networks. Information Processing Letters. 1978;7(6):277278.
Ahmed Faruque, AlAmin Khan Md, Rahman Khan Aminur, Ahmed Syed Sabbir, Sharif Uddin Md. An efficient algorithm for finding maximum flow in a networkflow. Journal of Physical Sciences. 2014;19:4150.
Orlin JB. Max flows in time, or better; 2018.
Available:https://dspace.mit.edu/openaccessdisseminate/1721.1/8820
Wikipedia maximum flow problem.
Available:https://en.wikipedia.org/wiki/Maximum_flow_problem
Fulkerson DR. An outofkilter method for minimal cost flow problems. Journal of the Society for Industrial and Applied Mathematics. 1961;9(1):1827.
Busacker RG, Gowen PG. A procedure for determining a family of minimum cost network flow patterns. Operations Research Office Technical Report 15, John Hopkins University, Baltimore; 1961.
Klein M. A primal method for minimum cost flows with applications to the assignment and transportation problems. Management Sci. 1967;14(3):205220.
Engquist M. A successive shortest path algorithm for the assignment problem. Research Report, Center for Cybernetic Studies (CCS) 375, University of Texas, Austin; 1980.
Carpaneto G, Toth P. Primaldual algorithms for the assignment problem. DAM. 1987;18:137153.
Orlin JB. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming. 1997;78(2):109–129.
Eroglu E. An application of the network simplex method for minimum cost flow problems. Balkan Journal of Mathematics. 2013;1:117130.
Tarjan RE. Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Mathematical Programming. 1997;78:16977.
Orlin JB. A faster strongly polynomial minimum cost flow algorithm. Operations Research. 1993;41(2):338350.
Parpalea Mircea. Interactive tool for the successive shortest paths algorithm in solving the minimum cost flow problem. Bulletin of the Transilvania University of Brasov, Series III: Mathematics, Informatics, Physics. 2009;2(51):255262.
Sokkalingam PT, Ahuja RK, Orlin JB. New polynomialtime cyclecancelling algorithms for minimum cost ﬂows. Networks. 2000;36:53–63.
Goldberg AV, Tarjan LE. Efficient maximum flow algorithms. Communications of the ACM. 2014;57:8289.
Syslo MM, Deo N, Kowalik JS. Discrete optimization algorithms with Pascal programs. Englewood Cliffs, New Jersey: PrenticeHall; 1983.
Moore EF. The shortest path through a maze. Proc. Int. Symp. On the Theory of Switching, Part II; 1957.
Bellmann RE. On a routing problem. Quart. Appl. Math. 1958;16:8790.
Pape U. Algorithm 562: Shortest path lengths. ACM Trans. Math. Software. 1980;5:450455.
Panyotova G, Slavona SL. Modelling network flow by excel solver. Trakia Journal of Sciences. 2009;8(3):1215.

Abstract View: 2364 times
PDF Download: 2887 times