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=-ΔTt. Here ΔT is the temperature decrement and t is the time (in Monte Carlo steps) at each temperature T. For the 2D ±J and Gaussian models, E(r)=E₀+C₁rˣ, where x0.25, while for the 3D ±J, a two-layer ±J, 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.