Optimization by Simulated Annealing
1983 · paper · Physics
Develops the analogy between statistical mechanics and combinatorial optimization, using the Metropolis algorithm to build simulated annealing. Applies it to computer design problems such as partitioning, placement and wiring, and to traveling salesman problems with thousands of cities.
Checked: PDF from cs.gettysburg.edu, fetched 5 Oct 2026. Page numbers are those of that PDF.
2 findings
Substance Eq. 11 prints "h_i = Σ_v ε_iv [2n_v(0) + Σ_j a_jv]", which is twice the linear coefficient that follows from Eq. 9 on the normalisation of Eq. 10 and Eq. 12 ("J_ij = Σ_v ε_iv ε_jv / 4").
- p. 8 Eq. 11
[2n
- p. 8 Eq. 12
(12)
Only the authors can say what is right here.
Judge's note: Viewed page 8 and an enlarged render of Eqs. 10-12. Own reworking: since a_iv = ε_iv², a_iv ε_iv = ε_iv, so Eq. 9 is n_v = (1/2)Σ_i ε_iv μ_i + A_v with A_v = (1/2)Σ_j a_jv + n_v(0). Then n_v² = (1/4)Σ_{i,j} ε_iv ε_jv μ_i μ_j + A_v Σ_i ε_iv μ_i + A_v². Summing over v with the double sum over all i,j as printed in Eq. 10 gives J_ij = Σ_v ε_iv ε_jv/4 (Eq. 12 as printed) and h_i = Σ_v ε_iv [n_v(0) + (1/2)Σ_j a_jv], half of Eq. 11. If instead the sum ran over distinct pairs, J would be 1/2 and h unchanged; multiplying F by 2 to match Eq. 11 would make J = 1/2 over all i,j. No convention makes Eqs. 11 and 12 agree. The form of the Hamiltonian (the paper's point) is unaffected, but the relative factor between J and h is wrong as printed.
Second check: another model agreed
Report a problem with this finding
Substance Low-density limit: "all the links have either one or no wires ... For this limit the best possible value of F will be N_W/N_L"; from the definition of F (sum over links of the squared number of wires) the value is N_W, not N_W/N_L.
- p. 8 Wiring section, right column, top
this limit the best possible value of F will
- p. 8 Wiring section, middle column, bottom
each link. In this limit F is bounded
- p. 8 Wiring, middle column, bottom
In this limit F is bounded
Only the authors can say what is right here.
Judge's note: Viewed page 8. F is defined as "the square of the number of wires on each link ... sum the squares for all links". The high-density bound printed, N_W²/N_L, equals N_L·(N_W/N_L)², so N_W is the total wire occupancy summed over links. Own reworking for the low-density case: n_v in {0,1} and Σ n_v = N_W give F = Σ n_v² = Σ n_v = N_W. N_W/N_L is the mean occupancy per link (below 1 here) and cannot be a sum of N_W ones. Nothing in the text redefines F per link for this sentence.
Second check: another model agreed
Report a problem with this finding
15 minor (typos and the like; most checked by the judge only)
Wording Below Eq. 7 the condition on the balance coefficient is "λ ≲ z/2" with "Choosing λ ≃ z/2" giving equal weight; one column later the spin-glass identification holds "as long as λN ≃ z/2". The two differ by a factor N and are not reconciled; the example uses λ = 0.01 with N ≈ 5000 (λN ≈ 50).
- p. 5 Text below Eq. 7
Choosing λ ≃ z/2
- p. 5 Right column, paragraph 'The identification of Eq. 7 as a spin glass Hamiltonian'
as long as λN ≃ z/2
- p. 5 below Eq. 7, left column
Reasonable values of λ should satisfy
- p. 5 right column, paragraph beginning 'The identification of Eq. 7'
problem, as long as λN ≃ z/2
Only the authors can say what is right here.
Judge's note: Viewed page 5: left column prints "λ ≲ z/2" and "Choosing λ ≃ z/2"; right column prints "as long as λN ≃ z/2". Page 6 gives λ = 0.01 for the ~5000-gate example. No text defines a rescaled λ or explains the factor N. The second condition may be a separate scaling statement (total antiferromagnetic field from N spins versus z local couplings) rather than a slip, so this is a question for the authors, not a correction.
Second check: another model agreed
Report a problem with this finding
Wording Text: "The finite temperature curves in Fig. 1 show the distribution of pins per chip for the configurations sampled at T = 2.5, 1.0, and 0.1"; Fig. 1 labels its six finite-temperature curves T=0.1, T=0.76, T=1.05, T=1.3, T=1.6 and T=2.4. No curve is labelled 2.5 or 1.0, and three plotted curves are not mentioned.
- p. 6 Partitioning text, middle column
the configurations sampled at T = 2.5, 1.0, and 0.1
- p. 5 Fig. 1 curve labels
T=2.4
- p. 6 Physical Design of Computers, paragraph beginning 'The finite temperature curves in Fig. 1'
the configurations sampled at T = 2.5,
- p. 5 Fig. 1, curve labels
T=1.05
Only the authors can say what is right here.
Judge's note: Viewed page 6 text and Fig. 1 on page 5 (plus an enlarged render). Labels read 0.1, 0.76, 1.05, 1.3, 1.6, 2.4 and ∞. Only 0.1 matches the text. The text values happen to fit the stated schedule T_n = 10·0.9^n (2.54, 0.985, 0.097), so the text and figure may come from different samplings; no statement in the paper reconciles them. Text misdescribes the figure; data themselves not shown to be wrong.
Second check: another model agreed
Report a problem with this finding
Wording Text says the Fig. 1 curves "show the distribution of pins per chip", while the figure's axis is "Sum of pins on the two chips" and the caption is "Distribution of total number of pins required in two-way partition".
- p. 6 Partitioning text, middle column
show the distribution of pins per chip
- p. 5 Fig. 1 x-axis label
Sum of pins on the two chips
- p. 5 Fig. 1 caption
Distribution of total number of pins
Judge's note: Viewed Fig. 1 (page 5) and the text on page 6. The T=∞ curve sits near 5800 on the axis, i.e. about twice the "3000 pins" each chip is said to need, and the quench arrow sits near 1400, about twice the "approximately 700 pins" per chip. So the figure plots the two-chip sum and the phrase "pins per chip" is loose wording; numbers are consistent once the factor of two is applied.
Second check: another model agreed
Report a problem with this finding
Wording Text: "For this sample run in the low-temperature limit, the two chips required 353 and 321 pins, respectively" (sum 674), but the T=0.1 curve in Fig. 1 sits at roughly 550-560 on the "Sum of pins on the two chips" axis; the paper does not say whether Fig. 1 and the quoted result are from the same run and balance score.
- p. 6 paragraph beginning 'The finite temperature curves in Fig. 1'
the two chips required 353 and 321
- p. 5 Fig. 1, leftmost curve
T=0.1
Only the authors can say what is right here.
Judge's note: Viewed Fig. 1 on page 5 and an enlarged render from the PDF. Axis 0 to 6000 spans about 730 px; the T=0.1 spike is about 68 px from 0, i.e. about 560, and the T=0.76 curve about 800. The axis reading is supported by the quench arrow at about 1400 (text: about 700 pins per chip) and T=∞ at about 5800. 674 would lie between the T=0.1 and T=0.76 curves. This is a read-off from a small plot (perhaps ±40), and Fig. 1 could come from a different run (the modified balance score gave 271+183=454), so it is a question for the authors rather than an established error.
Second check: another model agreed
Report a problem with this finding
Wording "All reduce the peak wire density on a link by more than 45 percent. Simulated annealing with Z-moves improved the random routing by 57 percent, averaging results for both x and y links": the quoted peaks (173 and 143 random; 105 and 96 with Z-moves) are reductions of 39% and 33% (mean 36%); 57% is reproduced only as the excess of the random peak over the annealed peak (65% and 49%), a base the wording does not state.
- p. 9 Wiring section, right column, text above 'Traveling Salesmen'
All reduce the peak wire density on a link by more than 45 percent
- p. 9 Wiring section, middle column
Fig. 6 are 173 (x direction) and 143 (y
- p. 9 Wiring section, right column, top
single link are 105 (x) and 96 (y)
- p. 9 Wiring, end of section (right column)
random routing by 57 percent
Only the authors can say what is right here.
Judge's note: Viewed page 9 text and Fig. 8 (enlarged render). Text gives 173 (x) and 143 (y) for Fig. 6 and 105 (x) and 96 (y) for Fig. 7. As reductions of the random value: 39.3% and 32.9%, mean 36.1%. As random/optimised − 1: 64.8% and 49.0%, mean 56.9%, which matches the printed 57. In Fig. 8 the random x-peak is about 173 and the methods peak at about 105-113 (35-39% lower; 53-65% on the other base), so "more than 45 percent" also holds only on the optimised base. The numbers are internally consistent under that convention, but "reduce ... by more than 45 percent" in its ordinary sense is not met by any method; the paper does not define the measure.
Second check: another model agreed
Report a problem with this finding
Wording The text says "The configurations studied below T = 0.8 (for instance, Fig. 9b)", but the Fig. 9 caption gives "(b) T = 0.8", so the example is at T = 0.8, not below it.
- p. 10 Traveling Salesmen, last paragraph
ied below T = 0.8 (for instance, Fig. 9b)
- p. 9 Fig. 9 caption
(b) T = 0.8,
Judge's note: Read the page 10 crop and the Fig. 9 caption crop on page 9. The text cites Fig. 9b as an instance of configurations below T = 0.8; the caption labels panel (b) as T = 0.8 exactly. No other statement in the article explains it. Most likely loose wording for "at and below T = 0.8"; either reading could be intended, so this is a minor wording point.
Second check: another model agreed
Report a problem with this finding
Typo Eq. 6 is printed "S(T) = S(T1) − ∫_T^T1 C(T′) dT / T": the integrand uses the dummy variable T′ in C(T′) but the differential and the denominator are the unprimed T, which is also the lower limit; integrating Eq. 5 gives C(T′) dT′/T′.
- p. 4 Eq. 6
C(T') dT
Judge's note: Viewed page 4 and an enlarged render of Eq. 6 from the PDF. The prime on C(T′) is clearly printed; dT and the T in the denominator have no prime. Integrating dS/dT = C/T from T to T1 gives the integral of C(T′)dT′/T′. A notational slip with an evident fix; the meaning is not in doubt, so cosmetic.
Second check: none (judge only)
Report a problem with this finding
Typo "where slower cooling with be helpful" should read "will be helpful".
- p. 8 End of Placement section, left column
where slower cooling with be helpful
Judge's note: Viewed page 8, end of the Placement section, left column: the printed word is "with". Not an extraction artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Reference 1 prints the author as "E. L. Lawlor, Combinatorial Optimization (Holt, Rinehart & Winston, New York, 1976)"; the author's name is Lawler.
- p. 10 References and Notes, ref. 1
E. L. Lawlor, Combinatorial Optimization
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that the author of Combinatorial Optimization (Holt, Rinehart & Winston, 1976) is E. L. Lawler. Viewed page 10 and an enlarged render of the reference list: the printed spelling is "Lawlor".
Second check: none (judge only)
Report a problem with this finding
Typo Reference 7 prints "E. Shrö-dinger, Statistical Thermodynamics (Cambridge Univ. Press, London, 1946)"; the name is Schrödinger (the "c" is missing).
- p. 10 References and Notes, ref. 7
E. Shrö-
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that the author of Statistical Thermodynamics (Cambridge Univ. Press, 1946) is E. Schrödinger. Viewed page 10 and an enlarged render: the name is printed "Shrö-" / "dinger" across a line break, without the c.
Second check: none (judge only)
Report a problem with this finding
Typo "steps joining regions more than one gap are eliminated": a word such as "apart" appears to be missing after "more than one gap".
- p. 10 Traveling Salesmen, paragraph on clustered cities, T = 1.2
steps joining regions more than one gap are eliminated
Judge's note: Read the crop on page 10. The printed text is as quoted, with no line lost. The clause is elliptical ("regions more than one gap [apart]"); the meaning is clear, and the terse form could be the authors' own wording, so this is cosmetic at most.
Second check: none (judge only)
Report a problem with this finding
Typo Reference 1 prints the author as "E. L. Lawlor, Combinatorial Optimization (Holt, Rinehart & Winston, New York, 1976)"; the author of that book is E. L. Lawler.
- p. 10
E. L. Lawlor, Combinutorial Optimization
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the author of Combinatorial Optimization: Networks and Matroids (Holt, Rinehart & Winston, 1976) is Eugene L. Lawler. The page image clearly prints "Lawlor". The "Combinutorial" in the reviewer's quote is an OCR artefact of the text layer; the page prints "Combinatorial" correctly, so only the surname is at issue.
Second check: none (judge only)
Report a problem with this finding
Typo Reference 12 prints "(Prentice-Hall, Engelwood Cliffs, N.J., 1972)"; the place name is Englewood Cliffs.
- p. 11 References and Notes, ref. 12
Engelwood Cliffs
- p. 11 References, ref. 12
Prentice-Hall, Engelwood Cliffs, N.J., 1972
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the New Jersey borough where Prentice-Hall published is spelled Englewood Cliffs. The crop of page 11 clearly shows "Engelwood Cliffs", so the misspelling is in the print and is not an extraction artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Reference 26 prints "D. J. Resenkrantz, R. E. Stearns, P. M. Lewis, SIAM (Soc. Ind. Appl. Math.) J. Comput. 6, 563 (1977)"; the first author's name is Rosenkrantz.
- p. 11 References and Notes, ref. 26
D. J. Resenkrantz
- p. 11 References and Notes, ref. 26
D. J. Resenkrantz, R. E. Stearns, P. M. Lewis
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the first author of the SIAM J. Comput. 6, 563 (1977) paper is D. J. Rosenkrantz. The page 11 image clearly shows "Resenkrantz" with an e as the second letter. The quote was not found in the text layer only because the OCR garbled the line ("i). ~.'Kesenkrantz"); the print itself is legible.
Second check: none (judge only)
Report a problem with this finding
Typo Reference 21 prints "A. J. Blodgett and D. R. Barbout, ibid. 26, 30 (1982)"; the co-author's name is Barbour.
- p. 11 References and Notes, ref. 21
D. R. Barbout
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the IBM J. Res. Dev. 26, 30 (1982) paper on the thermal conduction module is by A. J. Blodgett and D. R. Barbour. The page 11 image clearly shows "Barbout" ending in t. The text layer reads "D. K. Barbout" through OCR error, which is why the quote was not located; the print reads "D. R. Barbout".
Second check: none (judge only)