This function returns a metaheuristic that implements a simulated annealing behavior. This metaheuristic discards neighbors using a probabilistic rule based on the cost of the neighbor and a notion of temperature. We will describe the operation of this metaheuristic as if it is performing a minimization procedure, but maximization can also be performed. Given a current solution of cost c, a neighbor of cost c+d, a temperature of T, and a random number r in the range [0..1), then the neighbor is accepted under the following condition:

r <= exp(-d / T)

When the increase in cost d is not strictly positive, the move is never rejected. When the increase in cost provided by the move is positive, the move is rejected probabilistically. Larger increases in cost and lower temperatures both make rejection of the move more likely. The current temperature is maintained internally by the returned metaheuristic or stored in the variable temperature, so that it can be inspected if desired.

The random number generator rand is used to generate the numbers r for the rule above. A non-reversible random number generator is recommended, as a reversible one generates the same random number for each leaf tested. To avoid the problem of the different state of the random number generator during re-computation, the simulated annealing test above is only performed when in the original computation mode. No neighbors are rejected when recomputing.

The overall idea of simulated annealing is to begin search at a high temperature to allow degrading moves to be taken readily— which allows the search to wander. Over time, the temperature is reduced, causing the search to be less inclined to accept degrading moves. The parameter startTemperature defines the temperature at which to begin the simulated annealing metaheuristic. Each time that the notify method is called for the returned metaheuristic, the temperature is reduced by the following rule.

 currentTemperature = currentTemperature * reductionFactor

where reductionFactor can range from 0 to 1. Usually, reduction factors are greater than 0.99. A high reduction factor results in slower cooling and, usually, in a better final solution. However, the search takes longer to stabilize in this condition.

If the parameter cutoffProbability is specified, it can be used as an efficiency measure. If the chance of accepting a neighbor according to the above probability equation is less than cutoffProbability, then it is rejected. This is done at each move by setting the upper bound on the cost equal to:

c - T * ln (cutoffProbability)

where c is the current cost and T is the current temperature. This allows pruning of neighbors with cost greater than this value without using the probabilistic rule. A cutoff probability of 0 results in a “pure' simulated annealing algorithm.

The parameter freezingTemperature can be specified to define a lower limit on the temperature reduction. Calling IloMetaHeuristic::complete on the returned metaheuristic returns IloTrue if and only if this temperature has been met.

For more information, see IloRandom in the IBM ILOG Concert Technology Reference Manual.