Simulated Annealing

The idea

Floorplanning cost functions are rugged: full of local minima separated by ridges that greedy improvement cannot cross. Simulated annealing, borrowed from the statistical mechanics of cooling metals, escapes them with one rule. Propose a random move (any of the perturbations described on the representation pages). If it improves the cost, accept it. If it worsens the cost by Δ, accept it anyway with probability exp(−Δ / T), where T is a temperature that starts high (almost everything accepted, free exploration) and is lowered slowly (the system settles into a deep basin).

The theory is reassuring at infinite patience (with slow enough cooling, convergence to the global optimum has been proved) and silent at practical schedules, where manual tuning takes over: initial temperature chosen so a target fraction of moves accept, geometric cooling (T multiplied by 0.85 to 0.99 per stage), moves-per-stage scaled with problem size, and cost normalization so area and wirelength terms trade off stably.

Why floorplanning married it

The representation zoo exists because annealing only needs three things: a state encoding, a move set, and a cost evaluator. Polish expressions, sequence pairs, and B*-trees are all answers to "what state and moves give annealing the best-shaped space?" Nothing else matches its indifference to cost-function ugliness: add a fixed-outline penalty, a wirelength estimate, a thermal term, and the engine does not care.

Where you meet it today

Still the reference optimizer for hard-block packing and analog placement, and inside modern hierarchical macro placers (the leaf-level packer of Hier-RTLMP anneals). Its weakness, runtime that scales poorly to millions of movable objects, is exactly the gap analytical placement grew to fill.