Stoer, J., and Bulirsch, R. 1980, Introduction to Numerical Analysis (New York: Springer-Verlag), §. Wilkinson, ., and Reinsch, C. 1971, Linear Algebra, vol. II of Handbook for Automatic Computation (New York: Springer-Verlag). | 444 Chapter 10. Minimization or Maximization of Functions Stoer J. and Bulirsch R. 1980 Introduction to NumericalAnalysis New York Springer-Verlag . Wilkinson . and Reinsch C. 1971 Linear Algebra vol. II of Handbook for Automatic Computation New York Springer-Verlag . 5 s o S Simulated Annealing Methods 11 j w - o 3 X-X 0 Q n 3- V V The method of simulated annealing 1 2 is a technique that has attracted signif- 3 g icant attention as suitable for optimization problems of large scale especially ones E where a desired global extremum is hidden among many poorer local extrema. For o practical purposes simulated annealing has effectively solved the famous traveling i salesman problem of finding the shortest cyclical itinerary for a traveling salesman who must visit each of N cities in turn. Other practical methods have also been f 5 found. The method has also been used successfully for designing complex integrated 7 i circuits The arrangement of several hundred thousand circuit elements on a tiny 33 silicon substrate is optimized so as to minimize interference among their connecting wires 3 4 . Surprisingly the implementation of the algorithm is relatively simple. 3 Notice that the two applications cited are both examples of combinatorial minimization. There is an objective function to be minimized as usual but the space over which that function is defined is not simply the N -dimensional space of N continuouslyvariable parameters. Rather it is a discrete but very large configuration o 3 space like the set of possible orders of cities or the set of possible allocations of silicon real estate blocks to circuit elements. The number of elements in the fgo i CD CQ configuration space is factorially large so that they cannot be explored exhaustively. Furthermore since the set is discrete we are deprived of any notion of continuing downhill in a favorable direction. The concept of direction may not have any meaning in the configuration space. Below we
