The encyclopedia · Engineering & Operations · Technical decision · 1983
IBM escaped chip-layout local optima by annealing: accepting worse moves that cool
Kirkpatrick, Gelatt and Vecchi's 1983 simulated annealing accepted worse solutions early, then cooled, escaping chip-design optima that greedy search hit.
IBM Research
the move
VLSI chip wiring is placing thousands of components so total wire length is tiny. Greedy local search improves until it reaches a layout where no single move helps, but a better layout exists across a valley.
The 1983 Science paper by Kirkpatrick, Gelatt and Vecchi mapped this onto annealing solids. Accept a move that worsens the score with probability e^(−Δ/T), where the temperature T cools slowly over the run.
At high temperature almost any move is accepted, so the search wanders out of poor valleys; at low temperature it becomes greedy and descends into a good nearby optimum. The result beat the greedy layouts and became a broad optimisation tool.
why it works
- Escaping local optima requires sometimes moving downhill, which greedy search forbids.
- The temperature schedule trades exploration for exploitation without a prior estimate.
- It needs only a score, not gradients, so it solves discrete and messy problems.
- Cooling is controllable, so you can tune speed versus final quality.
what transfers
If a greedy method is always stuck in a local optimum, allow deliberately worse moves while a temperature parameter is high, then cool it. The randomness buys escape; the cooling buys convergence.
what came after
Simulated annealing became a workhorse for chip placement, circuit routing, scheduling and combinatorial design, and the template for a family of stochastic local-search methods across engineering and operations.
references
spotted an error? The archive wants to know.