Simulated annealing operates by allowing cost degrading moves based on a probabilistic rule. For the purposes of this description, we assume the objective is to be minimized, although both minimization and maximization can be performed within Solver. Given that the current solution has cost c, and the proposed solution has cost c + d (d can be positive or negative), simulated annealing accepts the new solution with probability:

Notice first that non-degrading moves are always accepted. Second, degrading moves are accepted with a probability which increases with a decrease in cost difference d, and a decrease in a parameter T. Ignoring T for the moment, we see that if a particular move degrades the cost by a large amount, it is less likely to be accepted than one which degrades the cost by a small amount.

The parameter T is known as the temperature and it controls the way the search operates. The effect of T is that for large T, cost degrading moves have a high chance of acceptance. For low T, the opposite situation holds, with only moves that slightly degrade the cost having any real chance of acceptance. The idea is to begin the search with T high, and gradually lower T as search progresses. This results in the search being able to roam freely near the beginning; by contrast, later on, when the temperature is low, the search looks more like greedy search, making only non-degrading moves.

It is worth noting that in simulated annealing, the moves to be examined must be drawn from the neighborhood in a random fashion. Otherwise, the moves specified first in the neighborhood will have a larger chance of acceptance than those that occur further on in the neighborhood which is contrary to the ethos of simulated annealing. A method for achieving this will be described later.

Controlling the simulated annealing search

Two things control how a simulated annealing search operates. The first is how the temperature is reduced as the search progresses. A common method, used in the predefined simulated annealing metaheuristic in Solver, is to reduce temperature after each move according to the rule:

T := T * factor

where factor is in the range [0..1), with values close to unity being preferred, as this reduces the temperature more slowly. As long as the temperature is allowed to reduce enough so that by the end of search the roaming behavior has ceased, a slower reduction of the temperature tends to result in better solutions. Of course, such a search also takes longer to run.

The second factor which controls the search is the initial temperature. If the initial temperature is set too high, search will roam for a very long time before settling. Thus it could take a very long time to produce a good solution as degrading moves are accepted too readily for too long. If the initial temperature is set too low, local minima may trap the search too quickly. Rearranging the probability acceptance equation, we have:

So, if we wish a cost degradation of d to be accepted with probability P(accept), at the beginning of search, then the initial value of T should be set to -d / ln(P(accept)). Normally, metaheuristics require some tuning for the problem being solved. These parameters for simulated annealing are examples of what to tune.