Document Type

Conference Proceeding

Publication Date



The Random House Dictionary defines anneal as " ... to free (glass, metals, etc.) from internal stress by heating and gradually cooling." In the physical world, impurities are annealed out of a substance by heating it to a high temperature. As it is cooled, its molecular structure gradually settles into a stable "low-energy" configuration. It is important to cool the substance slowly, especially at lower temperatures, so that impurities do not get "frozen" into place. With careful cooling, a low-energy state can eventually be reached. This state may not be the one with the lowest potential energy, where the spins of the electrons are uniformly aligned, but it is usually one where there are very few domainseach one containing electrons with approximately aligned spins.

There is a surprising analogy between the process described above and an algorithm that has proven to be successful in large classes of combinatorial optimization problems. The algorithm was formally introduced in its present form in 1983 by Kirkpatrick, Gelatt and Vecchi [5], although slightly different versions were used as early as 1953 by Metropolis et al. [9]. Because the algorithm searches for "optimized states" of certain combinatorial problems, and because it is guided by a control parameter (temperature) which is initially large and gradually becomes small, the algorithm has been given the name simulated annealing.


To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.