Introducing mass balancing theorem for network flow maximization

Abstract: Maximization of flow through the network is required in many practical applications such as water supply flow networks, Oil and Gas flow networks, and transportation networks etc. In this paper a new theorem is presented that has direct application on maximization of flow through the network. This theorem suggests that the maximization of network flow can be achieved by visiting only unbalanced nodes rather than the whole network. Therefore based on this theorem a method is developed that maximizes flow thorough the network by visiting only unbalanced nodes. Hence this method can achieve solution in a sub-linear time where network has fewer unbalanced nodes. However this method has worst case complexity of order O(m2-m), where m is the number of edges. Furthermore it is shown that this theorem has also potential to make optimization an easier task in a multi-commodity flow environment.

How to cite this paper

 Ursani, Z. (2012). Introducing mass balancing theorem for network flow maximization.International Journal of Industrial Engineering Computations , 3(5), 843-858.

Refrences

Ahuja, R. K., Magnanti, T. L., & Orlin J. B. (1988). Network flows. Working paper: OR 185-88.
Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA.
Ahuja, R. K., & Orlin, J. B. (1989). A fast and simple algorithm for the maximum flow problem. Operations Research, 37(5), 748-759.

Ahuja, R. K., & Orlin, J. B. (1991). Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems. Naval Research Logistics, 38, 413-430.

Albert, R., & Barabasi, A. L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1), 47-97.

Boldyreff, A. W. (1955). Determination of the maximal Steady State Flow of Traffic Through a Railroad Network. JORSA, 3(4), 443-465.

CATS. (2007). Combinatorial Algorithms Test Sets.

http://www.avglab.com/andrew/CATS/gens/, accessed January 2012.

Cherkasky, R. V. (1977). Algorithm for construction of maximum flow in networks with complexity of O(V2?E) operation. Mathematical Methods of Solution of Economical Problems, 7, 112-125 (in Russian).

Chandran, B. G., & Hochbaum, D. S. (2009). A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem. Operations Research Vol. 57, No. 2, March–April 2009, pp. 358–376 issn 0030-364X _ eissn 1526-5463 _ 09 _ 5702 _ 0358.

Danzig, G. B., & Fulkerson, D. R. (1956). On Max-Flow Min-Cut Theorem of Networks. In H.W. Kuhn and A. W. Tucker (ed.), Linear Inequalities and Related Systems, Annals of Mathematics Study 38, Princeton University Press, 215-221.

Dinic, E. A. (1970). Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dokl. 11, 1277-1280.

Dong, J., Wei, L., Cai, C., & Chen, Z. (2009). Draining algorithm for the maximum flow problem. International Conference on Communications and Mobile Computing.

Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19, 248-264.

Elias, P., Feinstein, A., & Shanon C. E. (1956). Note on maximum flow through a network. IRE Transactions on Information Theory, 117-119.

Ford, L. R. Jr., & Fulkerson D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399-404.

Gabow, H. N. (1985). Scaling algorithms for network problems. Journal of Computer and System Sciences, 31, 148-168.

Galil, Z. (1980). O(V5/3E2/3) algorithm for the maximum flow problem. Acta Informatica, 14, 221-242.

Goldberg, A. V. (1985). A new max-flow algorithm. Technical Report MIT/LCS/TM-291, Laboratory for Computer Science, MIT, Cambridge, Mass.

Goldberg, A. V., & Tarjan R. E. (1986). A new approach to the maximum flow problem, in Proc. 18th Annual ACM Symposium on the Theory of Computing. Association for Computing Machinery, New York, pp. 136-146.

Goldberg, A. V., & Tarjan, R.E. (1988). A New Approach to the Maximum-Flow Problem. Journal of the Association for Computing Machinery, 35(4), 921-940.

Hochbaum, D. S. (1997). The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem. Integer Programming and Combinatorial Optimization, 1412, 325-337.

Hochbaum D. S. (2001). A new-old algorithm for minimum-cut and maximum-flow in closure graphs. Networks, 37(4) 171-193.

Hochbaum D. S. (2003). A pseudoflow algorithm for the directed minimum cut problem. Manuscript, UC Berkeley.

Hochbaum, D. S., & Orlin, J.B. (2007). The pseudoflow algorithm in O(mnlog n2/m ) and O(n3). UC Berkeley manuscript. Submitted.

Hochbaum, D. S. (2008). The Pseudo-flow Algorithm. A new algorithm for the maximum flow problem. Operations Research (Informs) 56(4), 992-1009.

Karzanov, A. V. (1974). Determining the maximal flow in a network by the method of pre-flows. Soviet Mathematics Doklady, 15, 434-437.

Lerchs, H., & Grossman, I. (1965). Optimum design of open pit mines. Transactions, C.I.M, 68, 17-24.

Malhotra, V. M., Kumar, M. P., & Maheshwari S. N. (1978). An O(V3) Algorithm for Finding Maximum Flows in Networks. Information Processing Letters, 7, 277-278.

Orlin, J. B., & Ahuja R. K. (1987). New distance-directed algorithms for maximum flow and parametric maximum flow problems. Working Paper 1908-87, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA.

Radzik T. (1993). Parametric Flows, Weighted means of cuts, and fractional combinatorial optimization. In Complexity in Numerical Optimization, World Scientific, P. M. Pardalos Ed. 351-386.

Sawitzki D. (2004) Implicit flow maximization by iterative squaring. P. Van Emde Boas et al. (Eds.): SOFSEM 2004, Lecture Notes in Computer Science, 2932, 301–313.

Tarjan, R. E. (1984). A simple version of Karzanov’s blocking flow algorithm. Operations Research Letters, 2, 265-268.

Tarjan, R. E. (1986). Algorithms for Maximum Network Flow. Mathematical Programming, 26, 1-11.

Todinov, M. (2011A). Extended comments. A review of this paper, private communication, email dated: 04-02-2011.

Todinov, M. (2011B). Fast augmentation algorithms for maximising the flow in repairable flow networks after a component failure. IEEE 11th International Conference on Computer and Information Technology.