×
Effati, S.; Jafarzadeh, M.

Nonlinear neural networks for solving the shortest path problem. (English) Zbl 1124.65050

Appl. Math. Comput. 189, No. 1, 567-574 (2007).
The shortest path problem is reduced to the linear programming problem (LPP) in the spirit of M. S. Bazaraa, J. J. Jarvis and H. D. Sherali [Linear programming and network flows. 2nd ed. (John Wiley and Sons, New York etc) (1990; Zbl 0722.90042); 3rd ed. (2005; Zbl 1061.90085)]. Then the authors construct two reductions of LPPs to neural network models. The first one is constructed like the one of S. Effati and M. Bayman [Appl.Math.Comput.168, No. 2, 1370–1379 (2005; Zbl 1081.65054)]. An second one is inherently a sequential application of the penalty method and the gradient projection method to the LPP. An illustrative example is given.
Reviewer: Serghey G. Suvorov (Donetsk)

Cited in 2 Documents

MSC:

65K05 Numerical mathematical programming methods
90C05 Linear programming
90C35 Programming involving graphs or networks

Keywords:

linear programming; neural networks; optimization; shortest path problem; numerical example

Citations:

Zbl 1081.65054; Zbl 0722.90042; Zbl 1061.90085
Cite Review PDF
Full Text: DOI

References:

[1] Bodin, L.; Golden, B. L.; Assad, A.; Ball, M., Routing and scheduling of vehicles and crews: the state of the art, Comput. Oper. Res., 10, 2, 63-211 (1983)
[2] Ephremides, A.; Verdu, S., Control and optimization methods in communication network problems, IEEE Trans. Automat. Control, 34, 930-942 (1989) · Zbl 0709.94667
[3] Topkis, D. M., A shortest path algorithm for adaptive routing in communication networks, IEEE Trans. Commun., 36, 855-859 (1988) · Zbl 0654.90021
[4] Antonio, J. K.; Huang, G. M.; Tsai, W. K., A fast distributed shortest path algorithm for a class of hierarchically clustered data networks, IEEE Trans. Comput., 41, 710-724 (1992)
[5] Jun, S.; Shin, K. G., Shortest path planning in distributed workspace using dominance relation, IEEE Trans. Robot. Automat., 7, 342-350 (1991)
[6] Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart, and Winston: Holt, Rinehart, and Winston New York, pp. 59-108 · Zbl 0413.90040
[7] Bazaraa, M. S.; Jarvis, John J.; Sherali, H. D., Linear Programming and Network Flows (1992), John Wiley and Sons: John Wiley and Sons New York
[8] Effati, S.; Baymani, M., A new nonlinear neural network for solving convex nonlinear programming problems, Appl. Math. Comput., 3-4 (2004)
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.