Convergence of an annealing algorithm. (English) Zbl 0581.90061

The annealing algorithm is a stochastic optimization method which has attracted attention because of its success with certain difficult problems, including NP-hard combinatorial problems such as the travelling salesman, Steiner trees and others. There is an appealing physical analogy for its operation, but a more formal model seems desirable. In this paper we present such a model and prove that the algorithm converges with probability arbitrarily close to 1. We also show that there are cases where convergence takes exponentially long - that is, it is no better than a deterministic method. We study how the convergence rate is affected by the form of the problem. Finally we describe a version of the algorithm that terminates in polynomial time and allows a good deal of ’practical’ confidence in the solution.


90C10 Integer programming
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] A. Berman and R.J. Plemmons,Non-negative matrices in the mathematical sciences (Academic Press, New York, 1979). · Zbl 0484.15016
[2] V. Cerny, ”A thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm”,Journal of Optimization Theory and Applications (1984), to appear.
[3] A.W.F. Edwards, ”Minimal evolution” (Unpublished, 1966).
[4] B. Everitt,Cluster analysis (Heineman Educational Books, London, 1977). · Zbl 0507.62060
[5] M.R. Garey and D.S. Johnson,Computers and intractability: A guide to the theory of NP-completeness (W.H. Freeman, San Francisco, 1979). · Zbl 0411.68039
[6] S. Geman and D. Geman, ”Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images”,IEEE Transactions PAMI 6(6) (1984) 721–741. · Zbl 0573.62030
[7] D.P. Heyman and M.J. Sobel,Stochastic models in operations research, Volume 1: Stochastic processes and operating characteristics (McGraw-Hill Inc., New York, 1982). · Zbl 0503.90031
[8] D.S. Johnson, private communication, 1984.
[9] F.P. Kelly,Reversibility and stochastic networks (Wiley, Chichester, 1979). · Zbl 0422.60001
[10] S. Kirkpatrick, C.D. Gelatt, Jr. and M.P. Vecchi, ”Optimization by simulated annealing”, Research Report RC 9355, IBM (Yorktown Heights, NY, 1982). · Zbl 1225.90162
[11] M. Lundy, ”Applications of the annealing algorithm to combinatorial problems in statistics”,Biometrika 72 (1) (1985) 191–198. · doi:10.1093/biomet/72.1.191
[12] M. Lundy, ”The annealing algorithm”, Ph.D. Thesis, University of Cambridge (Cambridge, 1984).
[13] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth and A.H. Teller, ”Equation of state calculation by fast computing machines”,Journal of Chemical Physics 21 (1953) 1087–1092. · doi:10.1063/1.1699114
[14] F. Romeo and A. Sangiovanni-Vincentelli, ”Probabilistic hill-climbing algorithms: Properties and applications”, Memorandum No. UCB/ERL M84/34, University of California (Berkeley, CA, March 1984).
[15] B.M. Schwarzschild, ” Statistical mechanics algorithm for Monte Carlo optimization”, Physics Today (May 1982) 17–19.
[16] E. Seneta,Non-negative matrices and Markov chains (Springer-Verlag, New York, 2nd Edition, 1981). · Zbl 0471.60001
[17] E.A. Thompson, ”The method of minimum evolution”,Annals of Human Genetics 26 (1973) 333–340. · Zbl 0245.92012 · doi:10.1111/j.1469-1809.1973.tb00595.x
[18] C. Tovey, ”On the number of iterations of local improvement algorithms”,Operations Research Letters 2 (5) (1983) 231–238. · Zbl 0526.65045 · doi:10.1016/0167-6377(83)90030-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.