16.1 INTRODUCTION

Simulated annealing is a technique for finding an optimal or near-optimal solution for combinatorial optimization problems, or problems that have discrete variables. This technique was proposed by Kirkpatrick, Gelatt, and Vecchi in 1983 [1] and has been successfully applied to circuit partitioning, placement, and routing in the physical design of integrated circuits.

The goal of a combinatorial optimization algorithm is to find the state of lowest cost (or energy) from a discrete space of admissible configurations S. For each problem, a cost function must be defined that maps each state to a real number denoting its cost. For many problems, the number of possible states grows exponentially with the size of the input. Optimizing becomes the process of searching for the state of lowest cost in a hyper-dimensional space. With a large number of possible states to visit, the brute force method of visiting all configurations becomes impractical. Clearly, we need a search strategy to uncover the lowest cost solution in the jungle of states.

For many problems, the states of the configuration space are related. A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. These cases may be solved by either a greedy or a dynamic programming algorithm. In a greedy-choice problem, a globally optimal solution can be found by making a locally optimal (greedy) decision. The best choice is made at each moment; at each step, we solve the ramifications of the previous...