The Maximum Flow and Minimum Cost–Maximum Flow Problems: Computing and Applications
Asian Journal of Probability and Statistics,
The maximum flow and minimum cost-maximum 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 cost-maximum flow solutions to the following problems will also be discussed: maximum flow, minimum cost-maximum flow, transportation problem, assignment problem, shortest path problem, caterer problem.
- Maximum flow
- minimum cost-maximum flow
- objective function
- flow conservation and capacity constraints
- optimal solution
- network optimization
- transportation problem
- assignment problem
- shortest path problem
- caterer problem.
How to Cite
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): 63-74.
Schwartz BL. Possible winners in partially completed tournaments. SIAM Review. 1966;8(3):302-308.
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(1-2):83-97.
Lone MA, Mir SA, Wani MS. An application of assignment problem in agriculture using R. Journal of Scientific Research & Reports. 2017;13(2):1-5.
Hultberg TH, Cardoso DM. The teacher assignment problem: A special case of the fixed charge transportation problem. European Journal of Operation Research. 1997;101:463-473.
Feiyang Chen, Nan Chen, Hanyang Mao, Hanlin Hu. An application of bipartite matching in assignment problem. Chuangxinban Journal of Computing. 2018;1-2.
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):1215-1224.
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:399-404.
Dinitz Y. Algorithm for solution of a problem of maximum flow in a network with power estimation. Doklady Akademii Nauk SSSR. 1970;11:1277-1280.
Edmonds J, Karp JM. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM. 1972;19(2):248-264.
Goldberg AV, Tarjan RE. A new approach to the maximum flow problem. Journal of the ACM. 1988;35(4):921-940.
Goldberg AV, Rao S. Beyond the flow decomposition barrier. Journal of the ACM. 1998;45(5):783-797.
King V, Rao S, Tarjan R. A faster deterministic maximal flow algorithm. Journal of Algorithms. 1994;17:447-474.
Orlin JB. Max flows in O(nm) time, or better. STOC '13 Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing. 2013;765–774.
Sherman J. Nearly maximum flows in nearly linear time. Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science. 2013;263-269.
Malhotra VM, Pramodh-Kumar SN, Maheshwari SN. An algorithm for finding maximum flows in networks. Information Processing Letters. 1978;7(6):277-278.
Ahmed Faruque, Al-Amin Khan Md, Rahman Khan Aminur, Ahmed Syed Sabbir, Sharif Uddin Md. An efficient algorithm for finding maximum flow in a network-flow. Journal of Physical Sciences. 2014;19:41-50.
Orlin JB. Max flows in time, or better; 2018.
Wikipedia maximum flow problem.
Fulkerson DR. An out-of-kilter method for minimal cost flow problems. Journal of the Society for Industrial and Applied Mathematics. 1961;9(1):18-27.
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):205-220.
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. Primal-dual algorithms for the assignment problem. DAM. 1987;18:137-153.
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:117-130.
Tarjan RE. Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Mathematical Programming. 1997;78:169-77.
Orlin JB. A faster strongly polynomial minimum cost flow algorithm. Operations Research. 1993;41(2):338-350.
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):255-262.
Sokkalingam PT, Ahuja RK, Orlin JB. New polynomial-time cycle-cancelling algorithms for minimum cost ﬂows. Networks. 2000;36:53–63.
Goldberg AV, Tarjan LE. Efficient maximum flow algorithms. Communications of the ACM. 2014;57:82-89.
Syslo MM, Deo N, Kowalik JS. Discrete optimization algorithms with Pascal programs. Englewood Cliffs, New Jersey: Prentice-Hall; 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:87-90.
Pape U. Algorithm 562: Shortest path lengths. ACM Trans. Math. Software. 1980;5:450-455.
Panyotova G, Slavona SL. Modelling network flow by excel solver. Trakia Journal of Sciences. 2009;8(3):12-15.
Abstract View: 2364 times
PDF Download: 2887 times