APPLYING TABU SEARCH TO THE TWO-DIMENSIONAL ISING SPIN GLASS

A variety of problems in statistical physics, such as Ising-like systems, can be modeled as integer programs. Physicists have relied mostly on Monte Carlo methods to find approximate solutions to these computationally difficult problems. In some cases, optimal solutions to relatively small problems have been found using standard optimization techniques, e.g., cutting plane and branch-and-bound algorithms. Motivated by the success of tabu search (TS) in finding optimal or near-optimal solutions to combinatorial optimization problems in a number of different settings, we study the application of this methodology to Ising-like systems. Particularly, we develop a TS method to find ground states of two-dimensional spin glasses. Our method performs a search at different levels of resolution in the spin lattice, and it is designed to obtain optimal or near-optimal solutions to problem instances with several different characteristics. Results are reported for computational experiments with up to 64×64 lattices.