Optimization in Physics
In order to understand the characteristics of certain physics problems, it is helpful to study their minimum-energy states, or, if possible, the complete partition function. In this project, we focus on the area of disordered systems. Our goal is to provide effective methods and fast implementations for challenging physics problems. We focus on the design of exact solution procedures that always generate correct solutions, as this is often required by the application. A variety of our implementations is publicly available via the spin glass ground-state server.
Details about the physics models
Further details can also be found at http://cophy.informatik.uni-koeln.de/
Ising Spin Glasses
Algorithmically, minimizing the energy function for Ising spins is an unconstrained quadratic binary optimization problem that is well known to be equivalent to the max-2-cut problem. Given an edge-weighted graph, max-2-cut asks for partitioning the nodes into two disjoint sets maximizing the sum of the weights of edges connecting nodes in different partitions. Max-2-cut is in general an NP-hard problem that is also difficult in practice. For special graph classes, however, it allows solution in polynomial time. We develop exact approaches for both the NP-hard and the polynomially solvable cases of the max-2-cut problem and use them for the physics application.
Potts Spin Glasses
In a Potts spin glass, a spin can attain one of k states. The determination of energy-minimum states amounts to computing a maximum k-cut in the graph of interactions. Thus, the task is to partitioning the set of vertices of a graph into k disjoint subsets so as to maximize the total weight of the edges joining vertices in different partitions. We design and implement exact branch-and-cut algorithms based on semidefinite programming and cutting planes.
The problem of determining ground states of Coulomb glasses can be modelled as an equicut problem in a weighted complete graph. Given a partitioning of its nodes into two partitions of equal size, the equicut is defined as the set of edges joining nodes in different partitions. Computing an equicut with maximum weight is an NP-hard task. We design an exact branch-and-cut approach using general and problem-specific separation routines.Details on the coulomb glasses
Spin Glass Ground-State Server
As a service to the community, our implementations are publicly available via the spin-glass ground state server. Short- and long-range spin glass realizations of different dimensions can be submitted to the server, either through a web interface or using a command-line client. Big job batches are possible as well. Results are returned via e-mail.