Cooling-Rate Dependence for the Spin-Glass Ground-State Energy: Implications for Optimization by Simulated Annealing

The zero-temperature ground-state properties of five spin-glass models have been studied as a function of the cooling rate r=-t. Here is the temperature decrement and t is the time (in Monte Carlo steps) at each temperature T. For the 2D and Gaussian models, E (r) =E₀+C₁r^x, where x0. 25, while for the 3D, a two-layer, and infinite-range models, E (r) =E₀-C₂ (inr) ^-1. We speculate that this difference is related to the fact that the 2D models are not NP-complete while the other three models are.