Configuration Space Analysis for Optimization Problems

  • Sara A. Solla
  • Gregory B. Sorkin
  • Steve R. White
Conference paper
Part of the NATO ASI Series book series (volume 20)


An interesting analogy between frustrated disordered systems studied in condensed matter physics and combinatorial optimization problems [1] has led to the use of simulated annealing (a stochastic algorithm based on the Monte Carlo method) to find approximate solutions to complex optimization problems. A common feature of these systems is the competition between objectives which favor different and incompatible types of ordering. Such “frustration” leads to the existence of a large number of nearly degenerate solutions which are not related by symmetry.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    S. KIRKPATRICK, C.D. GELATT, JR., and M.P. VECCHI, Science 220, 671 (1983).CrossRefzbMATHMathSciNetGoogle Scholar
  2. 2.
    “Heidelberg Colloquium on Spin Glasses”, ed. by J.L. VAN HEMMEN and I. MORGENSTERN, Lecture Notes in Physics, Vol. 192 (Springer-Verlag, 1983).Google Scholar
  3. 3.
    G. TOULOUSE, Helv. Phys. Acta 57, 459 (1984); M: Mézard, this conference.Google Scholar
  4. 4.
    S. KIRKPATRICK and G. TOULOUSE, to appear in J. Physique.Google Scholar
  5. 5.
    S. KANG in “Proc. of the 20th Design Automation Conference”, (IEEE, 1983), p. 457Google Scholar
  6. 5a.
    C. ROWEN and J.L. HENNESSY in “Proc. of the Custom Integrated Circuits Conference”, to be published (IEEE, 1985).Google Scholar
  7. 6.
    M. ABRAMOWITZ and I.A. STEGUN, “Handbook of Mathematical Functions” (Dover, New York, 1965), p. 824.Google Scholar
  8. 7.
    M. MéZARD, G. PARISI, N. SOURLAS, G.TOULOUSE, and M. VIRASORO, Phys. Rev. Lett. 52, 1156 (1984)CrossRefGoogle Scholar
  9. 7a.
    N. PARGA, G. PARISI, and M. VIRASORO, J. Physique Lett. 45, L-1063 (1984).CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1986

Authors and Affiliations

  • Sara A. Solla
    • 1
  • Gregory B. Sorkin
    • 1
  • Steve R. White
    • 1
  1. 1.IBM Thomas J. Watson Research CenterYorktown HeightsUSA

Personalised recommendations