A theoretical framework for simulated annealing

Simulated Annealing has been a very successful general algorithm for the solution of large, complex combinatorial optimization problems. Since its introduction, several applications in different fields of engineering, such as integrated circuit placement, optimal encoding, resource allocation, logic synthesis, have been developed. In parallel, theoretical studies have been focusing on the reasons for the excellent behavior of the algorithm. This paper reviews most of the important results on the theory of Simulated Annealing, placing them in a unified framework. New results are reported as well.This research was sponsored by SRC and DARPA monitored by SNWSC under contract numbers N00039-87-C-012 and N00039-88-C-0292.