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=\frac{-\Delta T}{t}$. Here $\Delta T$ is the temperature decrement and $t$ is the time (in Monte Carlo steps) at each temperature $T$. For the 2D $\pm J$ and Gaussian models, $E\left(r\right)=E_0+C_1{r}^x$, where $x\cong 0.25$, while for the 3D $\pm J$, a two-layer $\pm J$, and infinite-range models, $E\left(r\right)=E_0-C_2{\left(\mathrm{inr}\right)}^{-1\mathrm{}}$. We speculate that this difference is related to the fact that the 2D models are not $\mathrm{NP}$-complete while the other three models are.