How does the simulated annealing acceptance rule actually work during detail placement, and why does the initial temperature matter?

Short Answer

Simulated annealing's acceptance rule: P=1 if the cost change (delta C) is <= 0 (always accept an improvement); P = exp(-delta C / T) if delta C > 0 (probabilistically accept a WORSE move, with probability shrinking as temperature T falls). The algorithm starts at a very high temperature and cools per an annealing schedule, so cost-increasing moves become progressively less likely as T falls -- eventually only cost-reducing moves are accepted. A higher initial temperature means more trials and longer runtime, since more of the early search space gets explored via probabilistically-accepted worse moves.

Technical Explanation

• Acceptance rule: P=1 if delta C <= 0 (an improving move is always accepted). P = exp(-delta C / T) if delta C > 0 (a worsening move is accepted probabilistically, with the probability governed by both the size of the worsening and the current temperature T).
• The algorithm starts at a VERY HIGH temperature and cools per a defined annealing schedule -- so cost-increasing moves become progressively less likely as T falls throughout the run.
• Eventually, as T approaches its final low value, only cost-reducing moves are accepted -- the search converges to a local (hopefully near-global) minimum rather than continuing to accept worse states.
• A HIGHER initial temperature means MORE trials and LONGER runtime -- because more of the early search space gets explored via probabilistically-accepted worse moves before the schedule cools enough to restrict acceptance.
• The objective function being optimized can be timing, congestion, or power -- simulated annealing is a general search strategy, not tied to one specific optimization goal.

Formula Or Decision Rule

P = 1 if delta C <= 0. P = exp(-delta C / T) if delta C > 0. Higher T means more probabilistic acceptance of worse moves; T decreases per the annealing schedule until only improving moves are accepted.

What To Check

• Warning sign: a detail placement run using simulated annealing takes far longer than expected, or converges to a surprisingly poor result.
• Inspect: check the initial temperature and annealing schedule -- too high an initial temperature explains long runtime; too fast a cooling schedule can explain premature convergence to a poor local minimum.
• Correct: tune the initial temperature and schedule to balance search thoroughness against runtime, rather than treating either symptom as an unrelated bug.

Healthy, Suspicious & Hard-stop Results

• Expected: detail placement runtime and result quality are consistent with the chosen initial temperature and annealing schedule -- neither surprisingly slow nor surprisingly poor.
• Investigate: detail placement takes unexpectedly long -- check whether the initial temperature is set higher than the design's search space actually warrants.
• Stop: a detail placement run is repeatedly re-tuned by trial and error without understanding that runtime and result quality are both direct, predictable consequences of the temperature/schedule settings.

What The Interviewer Is Testing

Whether you know the actual acceptance-probability formula and can explain WHY probabilistically accepting worse moves early on is a deliberate feature, not an algorithmic weakness.