A neural network approach to the maximum flow problem

Previous attempts to solve the maximum flow problem for the general multicommodity case have ended up with a linear programming formulation, in which the solution technique, based on the simplex algorithm, suffers from excessive storage and running time requirements, especially for large networks. An attempt is made to show how to apply neural network optimization techniques to solve the resulting linear programming problem in real time. For this purpose an extended version of the linear programming network proposed by L.O. Chua and G.N. Lin (1984, 1985) is suggested. The computational power of the extended model is demonstrated through computer simulations. The neural network hardware approach has the potential for a high computational speed due to the massive parallelism in computations that takes place at each processing element. This will make neural networks an interesting alternative for solving the maximum flow problem, as the search for the optimal solution is performed in real time