Zero-temperature instances

The Hamiltonian of the Edwards-Anderson Ising spin glass model is given by H = -Σ_<i,j> J_i,j σ_i σ_j , where the sum extends over nearest-neighbor bonds of a hyper-cubic lattice with bond-weigths J_i,j that are drawn at random from a distribution (Gaussian, bimodal, etc), typically symmetrical with zero mean and unit variance. It is believed that this model has a finite-temperature glass transition in dimensions d>2, and sampling equilibrium states at low (or zero) temperature is of interest.

Here are two instances (originally created for the 7th DIMACS Implementation Challenge on Semidefinite and related optimization problems) of spin glasses on three-dimensional lattices with periodic boundaries (torus) and a bimodal (J=±1) bond distribution for which ground states have been studied in some detail¹⁾:

- toruspm3-15-50 is an instance with N=15³=3375 spins and 10125 bonds. The best available bounds (thanks to F. Liers) established for this instance are H_lower = −6138.02 (from semi-definite programming) and H_upper = −5831 (from branch-and-cut). With the Extremal Optimization heuristic, H_EO = −6049 (or H/N = −1.7923) was found.

- toruspm3-8-50 is an instance with N=8³=512 spins and 1536 bonds. For this instance the bounds given are H_lower=-922 and H_upper=-912. With the Extremal Optimization heuristic, H_EO=-916 (or H/N = −1.7891) was found.

The format of both files consists of ”#spins #bonds” in the first line, followed by all bonds ”i j J_i,j” line-by-line, where the spin-indices “i j” refer to a sequential labeling of spins in the lattice.

The Hamiltonian of the mean-field SK spin glass model is given by H = -Σ_i,j J_i,j σ_i σ_j , where the sum extends now over all (^N₂) pairs of spins i,j with bond-weights J_i,j that are drawn at random from a distribution (Gaussian, bimodal, etc). Again, the distribution is typically symmetrical but possibly with a non-zero mean and a variance of 1/√N. Here, we focus on the bimodal (J=±1) distribution and choose zero mean and unit variance (to facilitate integer arithmetic), so that the energy-density is given by H/N^3/2.

Here is a simple demo-program (demoSK.c²⁾) that can

• output a random bond matrix of a chosen size N with reproducible random seed,
• provide a quick-n-dirty approximation to the ground state of the same instance with the Extremal Optimization heuristic. This demo is interactive and can variably give a quick result or provide a detailed exposėe of the heuristic.

Here is a testbed of 10 instances of SK spin glasses with J=±1 bonds of size N=1023 that has been used to compare Extremal Optimization (EO) and Hysteretic Optimization (HO)³⁾. HO does extremely well for SK but HO tends to fail for spin glasses on systems with low vertex-degree⁴⁾. EO results were obtained with the demo-program above, using N³/10 update steps. We can identify each instance by its balance between J=+1 and J=-1-bonds; the data file contains line-by-line the lower-triangular part of the (symmetric) bond-matrix, where “1” designates J=+1 and “0” stands for J=-1. The comparison is as follows: