Neural Networks and Optimization Problems - A Case Study: The Minimum Cost Spare Allocation Problem

We are interested in finding near-optimal solutions to hard optimization problems using Hopfield-type neural networks. The methodology is based on a basic property of such networks, that of reducing their `energy ' during evolution, leading to a local or global minimum. The methodology is presented and several different network models usually employed as optimizers (Analog Hopfield net with Simulated Annealing, Boltzmann Machine, Cauchy Machine and a hybrid scheme) are applied on the Minimum Cost Spare Allocation Problem (or equivalently Vertex Cover in bipartite graphs). The experimental results (compared with a conventional exact algorithm) demonstrate the advantages and limitations of the approach in terms of solution quality and computation time. Keywords: Hopfield Network, Boltzmann Machine, Cauchy Machine, Optimization, Optimal Spare Allocation. Neural networks were first used to solve optimization problems by Hopfield and Tank around 1985 ([HoTa85], [HoTa87]). Since then the fie..