Frustrated Systems: Ground State Properties via Combinatorial Optimization

Abstract

An introduction to the application of combinatorial optimization methods to ground state calculations of frustrated, disordered systems is given. We discuss the interface problem in the random bond Ising ferromagnet, the random field Ising model, the diluted antiferromagnet in an external field, the spin glass problem, the solid-on-solid model with a disordered substrate and other convex cost flow problems occurring in superconducting flux line lattices and traffic flow networks. On the algorithmic side we present a concise introduction to a number of elementary algorithms in combinatorial optimization, in particular network flows: the shortest path algorithm, the maximum-flow algorithms and minimum-cost-flow algorithms. We present a short glance at the minimum weighted matching and branch-and-cut algorithms.

40 pages LaTeX, uses Springer macros (lamuphys.sty included), 4 postscript-figures included. Manuscript of a lecture given on the Eotvos summer school in Physics: Advances in Computer Simulations, Budapest, July 16-20, 1996

Cited by in corpus (19)

• A physicist's approach to number partitioning
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• On the Effects of Changing the Boundary Conditions on the Ground State of Ising Spin Glasses
• Domain Wall Renormalization Group Study of XY Model with Quenched Random Phase Shifts
• Ground State Structure of Random Magnets
• Application of a minimum cost flow algorithm to the three-dimensional gauge glass model with screening
• Monotonicity and Thermodynamic Limit for Short Range Disordered Models
• Numerical study of the strongly screened vortex glass model in an external field
• Ground state properties of fluxlines in a disordered environment
• Monte Carlo simulation of stoquastic Hamiltonians
• Degeneracy Algorithm for Random Magnets
• Low-energy excitations in the three-dimensional random-field Ising model
• Statistical mechanics methods and phase transitions in optimization problems
• Ground states versus low-temperature equilibria in random field Ising chains
• Ground-States of Two Directed Polymers
• The Binomial Spin Glass
• Global risk minimization in financial markets
• Screened Vortex Lattice Model with Disorder
• Disorder induced roughening transition of many elastic lines in a periodic potential