Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-95-1-004

Exact ground states of Ising spin classes: new experimental results with a branch and cut algorithm

Diehl, M. and De Simone, C. and Jünger, Michael and Mutzel, Petra and Reinelt, Gerhard and Rinaldi, G.

MPI-I-95-1-004. January 1995, 17 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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$.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-95-1-004.pdfMPI-I-95-1-004.pdfMPI-I-95-1-004.ps.gz41 KBytes; 129 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-004
Hide details for BibTeXBibTeX
@TECHREPORT{DiehlDeSimoneJuengerMutzelReineltRinaldi,
  AUTHOR = {Diehl, M. and De Simone, C. and J{\"u}nger, Michael and Mutzel, Petra and Reinelt, Gerhard and Rinaldi, G.},
  TITLE = {Exact ground states of Ising spin classes: new experimental results with a branch and cut algorithm},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-95-1-004},
  MONTH = {January},
  YEAR = {1995},
  ISSN = {0946-011X},
}