Advertisement

Statistical Mechanics: a General Approach to Combinatorial Optimization

  • E. Bonomi
  • J. L. Lutton
Conference paper
  • 168 Downloads
Part of the NATO ASI Series book series (volume 20)

Abstract

The aim of this work was to investigate the possibility of using statistical mechanics as an alternative framework to study complex combinatorial optimization problems. This deep connection, suggested in ref. [1] by analogy with the annealing of a solid, allows to design a searching procedure which generates a sequence of admissible solutions. This sequence may be viewed as the random evolution of a physical system in contact with a heat-bath. As the temperature is lowered, the solutions approach the optimal solution in such a way that a well organized structure is brought out of a very large number of unpredictable outcomes. To speed up the convergence of this process, we propose a selecting procedure which favours the choice of neighbouring trial solutions. This improved version of the simulated annealing is illustrated by two examples: the N-city Travelling Salesman Problem [2] and the Minimum Perfect Euclidean Matching Problem [3].

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Science, 220 (1983) 671.zbMATHMathSciNetCrossRefGoogle Scholar
  2. 2.
    E. Bonomi, J. L. Lutton, SIAM Rev., 26 (1984) 551.zbMATHMathSciNetCrossRefGoogle Scholar
  3. 3.
    J. L. Lutton, E. Bonomi, “An Efficient Non-deterministic Heuristic for the Matching Problem”, submitted to Ann. Op. Res.Google Scholar
  4. 4.
    Ch. H. Papadimitriou, K. Steiglitz, “Combinatorial Optimization: Algorithms and Complexity”, Prentice-Hall, 1982.zbMATHGoogle Scholar
  5. 5.
    F. Romeo, A. Sangiovanni-Vincintelli, Memorandum No. UCB/ERL M84/34 University of California, Berkeley.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1986

Authors and Affiliations

  • E. Bonomi
    • 1
  • J. L. Lutton
    • 2
  1. 1.CPT Ecole PolytechniquePalaiseau CedexFrance
  2. 2.Cnet PAA/ATR/SSTIssy les MoulineauxFrance

Personalised recommendations