| Numéro |
J. Phys. France
Volume 46, Numéro 8, août 1985
|
|
|---|---|---|
| Page(s) | 1277 - 1292 | |
| DOI | https://doi.org/10.1051/jphys:019850046080127700 | |
DOI: 10.1051/jphys:019850046080127700
Configuration space analysis of travelling salesman problems
S. Kirkpatrick1 et G. Toulouse21 IBM T. J. Watson Research Center, Yorktown Heights, N.Y. 10598, U.S.A.
2 Laboratoire de Physique de l'E.N.S., 24, rue Lhomond, 75231 Paris Cedex 05, France
Abstract
The travelling salesman problem (TSP) and the Ising model of a spin glass are archetypes, respectively, of the combinatorial optimization problems of computer science and of the frustrated disordered systems studied in condensed matter physics. It has recently been proposed that these two fields have many phenomena in common. To see if, in fact, combinatorial optimization problems may be spin glasses, we define a random distance TSP as similar as possible to the idealized infinite-ranged model of spin glasses. Thermodynamic observables and internal correlations among locally stable configurations are analysed in the light of recent results for spin glasses. Evidence for freezing due to frustration and for a hierarchical, ultrametric structure of configuration space in this TSP is presented.
Résumé
Le problème du voyageur de commerce (TSP) et le modèle d'Ising d'un verre de spin sont, respectivement, des archétypes pour les problèmes d'optimisation combinatoire en informatique et pour les systèmes désordonnés frustrés en physique de la matière condensée. Il a été suggéré récemment que ces deux domaines ont beaucoup de phénomènes en commun. Pour voir si, de fait, les problèmes d'optimisation combinatoire peuvent être des verres de spin, nous définissons un TSP à distance aléatoire aussi semblable que possible au modèle idéalisé, à portée infinie, des verres de spin. A la lumière des résultats récents pour les verres de spin, nous analysons les observables thermodynamiques et les corrélations internes entre configurations localement stables. L'hypothèse d'un gel dû à la frustration et d'une structure hiérarchique ultramétrique dans l'espace des configurations est solidement argumentée, pour ce problème de voyageur de commerce.
7540 - Critical-point effects, specific heats, short-range order.
Key words
Ising model -- operations research -- spin glasses