Exact ground states of Ising spin glasses: New experimental results with a branch-and-cut algorithm

Simone, Caterina De and Diehl, Martin and Jünger, Michael and Mutzel, Petra and Reinelt, Gerhard and Rinaldi, Giovanni (1995) Exact ground states of Ising spin glasses: New experimental results with a branch-and-cut algorithm.
Published in: Journal of statistical physics Vol. 80 (1-2). pp. 487-496.


In this paper we study 2-dimensional Ising spin glasses on a grid with nearest neighbor and periodic boundary interactions, based on a Gaussian bond distribution, and an exterior magnetic field. We show how using a technique called branch-and-cut, the exact ground states of grids of sizes up to 100 times 100 can be determined in a moderate amount of computation time, and we report on extensive computational tests. With our method we produce results based on more than 20,000 experiments on the properties of spin glasses whose errors depend only on the assumptions on the model and not on the computational process. This feature is a clear advantage of the method over other more popular ways to compute the ground state, like Monte Carlo simulation including simulated annealing, evolutionary, and genetic algorithms, that provide only approximate ground states with a degree of accuracy that cannot be determined a priori. Our ground state energy estimation at zero field is -1.317.

Download: [img] Postscript - Preprinted Version
Download (164kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 116 (Google Scholar) | 62 (Web of Science)
Uncontrolled Keywords: branch-and-cut ground states spin glasses
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Related URLs:
Deposit Information:
ZAIK Number: zpr95-184
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 09 Jan 2012 10:39
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/184