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

DOI10.1007/BF02178370zbMath1106.82323OpenAlexW291625388WikidataQ56977314 ScholiaQ56977314MaRDI QIDQ2500052

Giovanni Rinaldi, Caterina De Simone, Michael Jünger, Petra Mutzel, Moritz Diehl, Gerhard Reinelt

Publication date: 23 August 2006

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02178370

zbMATH Keywords

Branch and cutIsing spin glassesexact ground states

Mathematics Subject Classification ID

Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Related Items

On the diameter of cut polytopes, Building an iterative heuristic solver for a quantum annealer, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, The spectral bundle method with second-order information, Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization, Quantum Annealing versus Digital Computing, Lifting and separation procedures for the cut polytope, A modeling and computational study of the frustration index in signed networks, The unconstrained binary quadratic programming problem: a survey, On optimization problems in acyclic hypergraphs, Boolean lexicographic optimization: algorithms \& applications, Exact ground states of two-dimensional \(\pm J\) Ising spin glasses, Incomplete inference for graph problems, Maximum Cut Parameterized by Crossing Number, Ground states of two-dimensional Ising spin glasses: fast algorithms, recent developments and a ferromagnet-spin glass mixture, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem, Adaptive extremal optimization by detrended fluctuation analysis, Canonical dual approach to solving the maximum cut problem, From equipartition to uniform cut polytopes: extended polyhedral results, Pseudo-Boolean optimization, A tight lower bound for a special case of quadratic 0-1 programming, Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Stochastic Tunneling Approach for Global Minimization of Complex Potential Energy Landscapes, The one-dimensional Ising model: mutation versus recombination, Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut, Mixed linear and semidefinite programming for combinatorial and quadratic optimization

Uses Software

• CPLEX

Cites Work

• The ground-state energy of the \(\pm J\) sping glass. A comparison of various biologically motivated algorithms
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• On the cut polytope