Spin glass, the travelling salesman problem, neural networks and all that

Abstract

This paper presents an overview of diverse topics that are seemingly different but interrelated, with strong connections to statistical mechanics on the one hand and spin glass physics on the other. Written primarily for an inter-disciplinary audience, we start with a brief recapitulation of the relevant aspects of statistical mechanics, particularly those needed for understanding the recently-popular simulated-annealing technique used in optimization studies. Then follows a survey of the spin glass problem, with particular attention to the consequences of quenched randomness. The travelling-salesman problem is considered next, as also the impact made on it by the spin glass problem. Several examples are then presented of optimization studies wherein the simulated-annealing concept has been profitably used. Attention is also drawn in this context to the lessons provided by the spin glass problem. Finally, a brief survey of neural networks is made, essentially from a physicist's point of view. The different learning schemes proposed are discussed, and the relevance of spin models and their statistical mechanics is also discussed.