×

A capable neural network model for solving the maximum flow problem. (English) Zbl 1239.90015

Summary: We present an optimization technique for solving a maximum flow problem arising in widespread applications in a variety of settings. On the basis of the Karush- Kuhn-Tucker (KKT) optimality conditions, a neural network model is constructed. The equilibrium point of the proposed neural network is then proved to be equivalent to the optimal solution of the original problem. It is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the maximum flow problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method.

MSC:

90B10 Deterministic network models in operations research
92B20 Neural networks for/in biological studies, artificial life and related topics
90C20 Quadratic programming
37B25 Stability of topological dynamical systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, A. K.; Orlin, J. B., A capacity scaling algorithm for the constrained maximum flow problem, Networks, 25, 89-98 (1995) · Zbl 0821.90041
[2] Caliskan, C., A double scaling algorithm for the constrained maximum flow problem, Computers and Operations Research, 35, 1138-1150 (2008) · Zbl 1172.90328
[3] Caliskan, C., On a capacity scaling algorithm for the constrained maximum flow problem, Networks, 53, 229-230 (2009) · Zbl 1176.90064
[4] Caliskan, C., A specialized network simplex algorithm for the constrained maximum flow problem, European Journal of Operational Research, 210, 137-147 (2011) · Zbl 1210.90036
[5] Ford, L. R.; Fulkerson, D. R., Maximum flow through a network, Canadian Journal of Mathematics, 8, 399-404 (1956) · Zbl 0073.40203
[6] Fulkerson, D. R., Increasing the capacity of a network: the parametric budget problem, Management Science, 5, 473-483 (1959) · Zbl 0995.90517
[7] Malek-Zavarei, M.; Frisch, I. T., A constrained maximum flow problem, International Journal of Control, 14, 549-560 (1971) · Zbl 0226.90009
[8] Tank, D. W.; Hopfield, J. J., Simple neural optimization networks: an A/D converter, signal decision circuit, and a linear programming circuit, IEEE Transactions on Circuits and Systems, 33, 533-541 (1986)
[9] Ding, K.; Huang, N.-J., A new class of interval projection neural networks for solving interval quadratic program, Chaos, Solitons and Fractals, 35, 718-725 (2008) · Zbl 1137.90020
[10] Effati, S.; Ranjbar, M., Neural network models for solving the maximum flow problem, Applications and Applied Mathematics, 3, 149-164 (2008) · Zbl 1175.90060
[11] Effati, S.; Ghomashi, A.; Nazemi, A. R., Application of projection neural network in solving convex programming problems, Applied Mathematics and Computation, 188, 1103-1114 (2007) · Zbl 1121.65066
[12] Effati, S.; Nazemi, A. R., Neural network models and its application for solving linear and quadratic programming problems, Applied Mathematics and Computation, 172, 305-331 (2006) · Zbl 1093.65059
[13] Friesz, T. L.; Bernstein, D. H.; Mehta, N. J.; Tobin, R. L.; Ganjlizadeh, S., Day-to-day dynamic network disequilibria and idealized traveler information systems, Operation Research, 42, 1120-1136 (1994) · Zbl 0823.90037
[14] Hu, X., Applications of the general projection neural network in solving extended linear-quadratic programming problems with linear constraints, Neurocomputing, 72, 1131-1137 (2009)
[15] Hu, X.; Wang, J., Design of general projection neural networks for solving monotone linear variational inequalities and linear and quadratic optimization problems, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 37, 1414-1421 (2007)
[16] Kennedy, M. P.; Chua, L. O., Neural networks for nonlinear programming, IEEE Transactions on Circuits and Systems, 35, 554-562 (1988)
[17] Lillo, W. E.; Loh, M. H.; Hui, S.; Zăk, S. H., On solving constrained optimization problems with neural networks: a penalty method approach, IEEE Transactions on Neural Networks, 4, 931-939 (1993)
[18] Maa, C. Y.; Shanblatt, M. A., Linear and quadratic programming neural network analysis, IEEE Transactions on Neural Networks, 3, 580-594 (1992)
[19] Nazemi, A. R., A dynamic system model for solving convex nonlinear optimization problems, Communications in Nonlinear Science and Numerical Simulation, 17, 1696-1705 (2012) · Zbl 1250.90067
[20] Nazemi, A. R., A dynamical model for solving degenerate quadratic minimax problems with constraints, Journal of Computational and Applied Mathematics, 236, 1282-1295 (2011) · Zbl 1229.90262
[21] Tao, Q.; Cao, J.; Sun, D., A simple and high performance neural network for quadratic programming problems, Applied Mathematics and Computation, 124, 251-260 (2001) · Zbl 1162.90532
[22] Xia, Y.; Feng, G.; Wang, J., A recurrent neural network with exponential convergence for solving convex quadratic program and related linear piecewise equation, Neural Networks, 17, 1003-1015 (2004) · Zbl 1068.68130
[23] Xia, Y.; Feng, G., An improved network for convex quadratic optimization with application to real-time beamforming, Neurocomputing, 64, 359-374 (2005)
[24] Xia, Y., A new neural network for solving linear and quadratic programming problems, IEEE Transactions on Neural Networks, 7, 1544-1547 (1996)
[25] Xia, Y.; Wang, J., A general projection neural network for solving monotone variational inequality and related optimization problems, IEEE Transactions on Neural Networks, 15, 318-328 (2004)
[26] Xia, Y.; Wang, J., A recurrent neural network for nonlinear convex optimization subject to nonlinear inequality constraints, IEEE Transactions on Circuits and Systems, 51, 447-458 (2004)
[27] Xue, X.; Bian, W., A project neural network for solving degenerate convex quadratic program, Neurocomputing, 70, 2449-2459 (2007)
[28] Xue, X.; Bian, W., A project neural network for solving degenerate quadratic minimax problem with linear constraints, Neurocomputing, 72, 1826-1838 (2009)
[29] Vegas, J. M.; Zufiria, P. J., Generalized neural networks for spectral analysis: dynamics and Liapunov functions, Neural Networks, 17, 233-245 (2004) · Zbl 1121.68398
[30] Wu, H.; Shi, R.; Qin, L.; Tao, F.; He, L., A nonlinear projection neural network for solving interval quadratic programming problems and its stability analysis, Mathematical Problems in Engineering, 1-13 (2010) · Zbl 1195.90072
[31] Yang, Y.; Cao, J., Solving quadratic programming problems by delayed projection neural network, IEEE Transactions on Neural Networks, 17, 1630-1634 (2006)
[32] Yang, Y.; Cao, J., A delayed neural network method for solving convex optimization problems, International Journal of Neural Systems, 16, 295-303 (2006)
[33] Yang, Y.; Cao, J., A feedback neural network for solving convex constraint optimization problems, Applied Mathematics and Computation, 201, 340-350 (2008) · Zbl 1152.90566
[34] Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D., Linear Programming and Network Flows (1990), Wiley: Wiley New York · Zbl 0722.90042
[35] Ortega, T. M.; Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables (1970), Academic Press: Academic Press New York · Zbl 0241.65046
[36] Datta, B. N., Numerical Methods for Linear Control Systems (2003), Elsevier Academic Press: Elsevier Academic Press San Diego, CA
[37] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1058.90049
[38] Miller, R. K.; Michel, A. N., Ordinary Differential Equations (1982), Academic Press: Academic Press New York · Zbl 0499.34024
[39] Amann, H., Ordinary Differential Equations: An Introduction to Nonlinear Analysis (1990), Walter de Gruyter: Walter de Gruyter Berlin
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.