Combinatorial Optimization with Neural Networks

A general introduction to the use of feed-back artificial neural networks (ANN) for obtaining good approximate solutions to combinatorial optimization problems is given, assuming no previous knowledge in the field. In particular we emphasize a novel neural mapping technique which efficiently reduces the solution space. This approach maps the problems onto Potts glass rather than spin glass models. The real strength in mapping optimization problems onto neural systems lies in the fact that local minima in the cost functions can be avoided with the use of mean field equations. The system ``feels'' its way towards good solutions. In the settling process it may encounter phase transitions. A systematic prescription can be given for estimating the phase transition temperatures in advance, which facilitates an automatized choice of optimal parameters. This analysis, which can be performed for both serial and synchronous updating of the mean field theory equations, also makes it possible to consistently avoid chaotic behaviour. These techniques are illustrated for the graph partition and the traveling salesman problems (TSP). Also, a realistic high school scheduling problem is dealt with in some detail. These problems are all characterized by equality constraints. The formalism can also be modified to deal with inequality constraints. This is illustrated with the knapsack problem. We also discuss the deformable templates approach, which is closely related to the Potts neural encoding. In problems of geometrical nature like TSP and track finding this method is more economical with its fewer degrees of freedom