Simulated annealing

In the early 1980s, Kirkpatrick et al. [1] and, independently, Černý [2] introduced simulated annealing as a randomized local search algorithm to solve combinatorial optimization problems. In a combinatorial optimization problem we are given a finite or countably infinite set of solutions S and a cost function f that assigns a cost to each solution. The problem is to find a solution i^∗ ∈ S for which f (i^∗) is either minimal or maximal, depending on whether the problem is a minimization or a maximization problem. Such a solution i^∗ is called a (globally) optimal solution. Without loss of generality, we restrict ourselves in this chapter to minimization problems.