J. Physique Lett. 45, 1145-1153 (1984)
DOI: 10.1051/jphyslet:0198400450240114500

On the statistical mechanics of optimization problems of the travelling salesman type

J. Vannimenus et M. Mézard

Laboratoire de Physique Théorique, ENS, 24, rue Lhomond, 75231 Paris Cedex 05, France

Abstract
We show that two very different temperature regimes exist for problems of the travelling salesman type, and that the annealed approximation is valid for the high-temperature regime. Random-link models are introduced, for which upper and lower bounds on the free energy are obtained in the low-temperature regime. A soluble model is presented, which possesses a phase transition strongly reminiscent of the spin-glass transition.

Résumé
Nous montrons qu'il existe deux régimes très différents en température pour les problèmes du type voyageur de commerce, et que l'approximation recuite est correcte dans le régime de haute température. Nous introduisons des modèles de liaisons aléatoires et obtenons des bomes inférieure et supérieure pour leur énergie libre, dans le régime basse température. Nous présentons un modèle soluble, qui possède une transition de phase rappelant fortement la transition verre de spin.

PACS
1180 - Optimisation techniques.
1290Z - Other applications of systems theory.

Key words
operations research -- optimisation -- statistical mechanics -- free energy bounds -- travelling salesman problems -- random link models -- optimization problems -- temperature regimes -- annealed approximation -- soluble model -- phase transition -- spin glass transition