×
Eglese, R. W.

Simulated annealing: A tool for operational research. (English) Zbl 0699.90080

Eur. J. Oper. Res. 46, No. 3, 271-281 (1990).
Summary: This paper describes the simulated annealing algorithm and the physical analogy on which it is based. Some significant theoretical results are presented before describing how the algorithm may be implemented and some of the choices facing the user of this method. An overview is given of the experience of experimenters with SA and some suggestions are made for ways to improve the performance of the algorithm by modifying the ‘pure’ SA approach.

Cited in 87 Documents

MSC:

90C27 Combinatorial optimization
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
65K05 Numerical mathematical programming methods

Keywords:

heuristics; simulated annealing
PDF BibTeX XML Cite
\textit{R. W. Eglese}, Eur. J. Oper. Res. 46, No. 3, 271--281 (1990; Zbl 0699.90080)
Full Text: DOI

References:

[1] Aarts, E. H.L.; Korst, J. H.M., Simulated Annealing and Boltzmann Machines (1989), Wiley: Wiley Chichester
[2] Aarts, E. H.L.; Laarhoven, P. J.M.van, Statistical cooling: A general approach to combinatorial optimization problems, Philips Journal of Research, 40, 193-226 (1985)
[3] Alspector, J.; Allen, R. B., A neuromorphic VLSI learning system, (Losleben, P., Advanced Research in VLSI (1987), MIT Press: MIT Press Cambridge, MA), 313-349
[4] Anily, S.; Federgruen, A., Simulated annealing methods with general acceptance probabilities, Journal of Applied Probability, 24, 657-667 (1987) · Zbl 0628.60046
[5] Bland, J. A.; Dawson, G. P., Tabu search applied to layout optimisation (1989), Department of Maths, Stats and O.R., Trent Polytechnic: Department of Maths, Stats and O.R., Trent Polytechnic UK, presented at CO89, Leeds, July 1989
[6] Casotto, A.; Romeo, F.; Sangiovanni-Vincentelli, A. L., A parallel simulated annealing algorithm for the placement of macro-cells, IEEE Transactions on Computer-Aided Design, 6, 838-847 (1987)
[7] Cerny, V., Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimisation Theory and Application, 45, 41-51 (1985) · Zbl 0534.90091
[8] Chams, M.; Hertz, A.; de Werra, D., Some experiments with simulated annealing for colouring graphs, European Journal of Operational Research, 32, 260-266 (1987) · Zbl 0626.90067
[9] Collins, N. E.; Eglese, R. W.; Golden, B. L., Simulated annealing—An annotated bibliography, American Journal of Mathematical and Management Sciences, 8, 209-307 (1988) · Zbl 0669.65047
[10] Connolly, D. T., Combinatorial optimization using simulated annealing, (presented at the Martin Beale Memorial Symposium. presented at the Martin Beale Memorial Symposium, London, July 1987 (1987), London School of Economics: London School of Economics London), WC2A 2AE
[11] Connolly, D. T., An improved annealing scheme for the QAP, European Journal of Operational Research, 46, 93-100 (1988) · Zbl 0715.90079
[12] Eglese, R. W.; Rand, G. K., (Conference seminar timetabling. Conference seminar timetabling, Journal of the Operational Research Society, 38 (1987)), 591-598
[13] Faigle, U.; Schrader, R., On the convergence of stationary distributions in simulated annealing algorithms, Information Processing Letters, 27, 189-194 (1988) · Zbl 0638.65054
[14] Farhat, N. H., Optoelectric analogs of self-programming neural nets: Architecture and methodologies for implementing fast stochastic learning by simulated annealing, Applied Optics, 26, 5093-5103 (1987)
[15] Glover, F.; Greenberg, H. J., New approaches for heuristic search: A bilateral linkage with artificial intelligence, European Journal of Operational Research, 39, 119-130 (1989) · Zbl 0658.90079
[16] Greene, J. W.; Supowit, K. J., Simulated annealing without rejected moves, IEEE Transactions on Computer-Aided Design, 5, 221-228 (1986)
[17] Grover, L. K., A new simulated annealing algorithm for standard cell placement, (Proc. IEEE International Conference on Computer-Aided Design. Proc. IEEE International Conference on Computer-Aided Design, Santa Clara (1986)), 378-380
[18] Hajek, B., Cooling schedules for optimal annealing, Mathematics of Operations Research, 13, 311-329 (1988) · Zbl 0652.65050
[19] Hertz, A.; de Werra, D., Using tabu search techniques for graph colouring, Computing, 39, 345-351 (1987) · Zbl 0626.68051
[20] Jerrum, M.; Sinclair, A., Approximating the permanent, (Internal report CSR-275-88 (1988), Department of Computer Science, University of Edinburgh) · Zbl 0723.05107
[21] Johnson, D. S.; Aragon, C. R.; McGeogh, L. A.; Schevon, C., Optimization by simulated annealing: An experimental evaluation, Part I (1987), AT&T Bell Laboratories: AT&T Bell Laboratories Murray Hill, NJ, preprint
[22] Johnson, D. S.; Aragon, C. R.; McGeogh, L. A.; Schevon, C., Optimization by simulated annealing: An experimental evaluation, Part II (1988), AT&T Bell Laboratories: AT&T Bell Laboratories Murray Hill, NJ, preprint
[23] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[24] Laarhoven, P. J.M.van, Theoretical and computational aspects of simulated annealing, (PhD thesis (1988), Erasmus University: Erasmus University Rotterdam) · Zbl 0659.90062
[25] Laarhoven, P. J.M.van; Aarts, E. H.L., Simulated Annealing: Theory and Applications (1987), Reidel: Reidel Dordrecht · Zbl 0643.65028
[26] Laarhoven, P. J.M.van; Aarts, E. H.L.; Lint, J. H.van; Wille, L. T., New upper bounds for the football pool problem for 6, 7 and 8 matches, Journal of Combinatorial Theory A (1988), in press · Zbl 0724.90085
[27] Lundy, M.; Mees, A., Convergence of an annealing algorithm, Mathematical Programming, 34, 111-124 (1986) · Zbl 0581.90061
[28] Maffioli, F., Randomized heuristics for NP-hard problems, (Andreatta, G.; Mason, F.; Serafini, P., Advanced School on Stochastics in Combinatorial Optimisation (1987), World Scientific: World Scientific Singapore), 76-93
[29] Matsuo, H.; Suh, C. J.; Sullivan, R. S., A controlled search simulated annealing method for the general jobshop scheduling problem, (Working paper #03-04-88 (1988), Department of Management, The University of Texas at Austin: Department of Management, The University of Texas at Austin Austin)
[30] Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, E., Equation of state calculations by fast computing machines, Journal of Chemical Physics, 21, 1087-1092 (1953) · Zbl 1431.65006
[31] Mitra, D.; Romeo, F.; Sangiovanni-Vincentelli, A. L., Convergence of finite-time behaviour of simulated annealing, Advances in Applied Probability, 18, 747-771 (1986) · Zbl 0604.60067
[32] Romeo, F.; Sangiovanni-Vincentelli, A. L., Probabilistic hill climbing algorithms: Properties and applications, (Proc. Chapel Hill Conference on VLSI. Proc. Chapel Hill Conference on VLSI, Chapel Hill, NC (1985)), 393-417
[33] Sasaki, G. H.; Hajek, B., The time complexity of maximum matching by simulated annealing, Journal of the ACM, 35, 387-403 (1988) · Zbl 0825.68416
[34] Tovey, C. A., Simulated simulated annealing, American Journal of Mathematical and Management Sciences, 8, 389-407 (1988) · Zbl 0684.65059
[35] Wille, L. T., The football pool problem for 6 matches: A new upper bound obtained by simulated annealing, Journal of Combinatorial Theory A, 45, 171-177 (1987) · Zbl 0667.05018
[36] Wright, M. B., Applying stochastic algorithms to a locomotive scheduling problem, Journal of the Operational Research Society, 40, 187-192 (1989) · Zbl 0658.90052
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.