Simulated Annealing (SA) has advantages and disadvantages compared to other global optimization techniques, such as genetic algorithms, tabu search, and neural networks. Among its advantages are the relative ease of implementation and the ability to provide reasonably good solutions for many combinatorial problems. Though a robust technique, its drawbacks include the need for a great deal of computer time for many runs and carefully chosen tunable parameters [EFC98].

With the existence of uphill moves, comes the possibility of cycles and random walks, both which stymie SA and are addressed in Section 4.1.6 (page ). Like hillclimbers, simulated annealing can fall into a local minima far from the global optimum solution (like premature crystalization) [Rib].

Without attempting to provide a comprehensive comparison of global optimization techniques, we present our approach and findings within the specific problem domain of improving dorm room assignments, using simulated annealing.

Given a neighborhood structure, simulated annealing can be viewed as an algorithm that continuously attempts to transform the current configuration into one of its neighbors [vLA87].

Simulated annealing, a Monte Carlo method that can be modeled
mathematically using the theory of finite Markov chains
[AKvL97]. By definition, a *Markov chain* is a sequence of
trials, where the probability of the outcome of a given trial depends
only on the outcome of the previous trial. In the case of SA, a trial
corresponds to a move, and the set of outcomes is given by a finite
set of neighboring states. Each move depends only on the outcome of
the previous attempt, so the concept of Markov chains applies. Since
the number of the trial does not affect the probabilities, it is
considered *homogenous* [AKvL97].

To govern the convergence of the algorithm, a set of parameters, known
as a *cooling schedule*, are specified by:

- an initial value of the control parameter (i.e. temperature)
- a decrement function for lowering the value of the control parameter
- a final value of the control parameter specified by a stop criterion
- a finite length of each homgeneous Markov chain.

Determining these parameters is one challenge with annealing. There is
much

research on the topic, dealing mostly with heuristic
schedules [Pic87,BGNZ96,AKvL97]. There are two main
categories of heuristic schedules: Static and dynamic. In a *static* cooling schedule, the parameters are fixed and cannot be
changed during the execution of the algorithm. With a *dynamic*
cooling schedule the parameters are adaptively changed during the
execution. The *Mathematical Optimization* chapter of the Computer
Science Education Project [CSE96] provides an introduction to two
simple static cooling schedules:

The simplest and most common temperature decrement rule is:

, where is a constant close to, but smaller than, 1. Thisexponential cooling scheme(ECS) was first proposed by Kirkpatrick et al. [KGV82] with .

Randelman and Grest [RG86] compared this strategy with alinear cooling scheme(LCS) in which is reduced every trials [while avoiding negative temperatures]: . They found the reductions achieved using the two schemes to be comparable, and also noted that the final value of [the objective function] was, in general, improved with slower cooling rates, at the expense, of course, of greater computational effort. Finally, they observed that the algorithm performance depended more on the cooling rate, , than on the individual values of and .

Some general guidelines exist when choosing an annealing schedule, for instance, there is a trade-off between large decrements of the control parameter () and small Markov chain lengths () -- usually small decrements of , or a ceiling for , polynomial in the problem size, are chosen to avoid long chains. When the Markov chain length is fixed, it may be related to the size of the neighborhoods in the problem instance. Apparently, when a sufficently long schedule is used, simulated annealing replaces iterative improvement as the optimal schedule [vLA87,AKvL97].

Researchers have proposed more elaborate, mostly adaptive, annealing schedules, using statistical measures to modify the control parameters. Unexpectedly, non-monotonic schedules have been observed as optimal in some situations [vLA87,AKvL97].