Research
HomeCurrent Resarch
In the COPhy project, we are interested in solving optimization tasks occuring in theoretical physics. Optimization problems occur in a number of physics applications, e.g. in complex systems such as Ising spinn glasses, Potts glasses, flux lines etc.
Taking the viewpoint of mathematical optimization and computer science, our goal is to provide effective algorithms and fast implementations for challenging physics problems. We focus on the desing of exact algorithms that are known to always generate correct solutions. Furthermore, a variety of our implementations can be used by anyone who is interested via the spin-glass ground state server, which we will further expand in the future.
This project has a interdisciplinary nature. Together with our physics colleagues, we study the physical properties of the systems by analyzing the data generated with our programs.
We are also interested in developing exact solution methods for applications apart from physics, mainly for NP-hard optimization problems.
Title: | Exact Ground-States of Planar Ising Spin Glasses | |||
Abstract: | We work on an algorithm for the calculation of ground-state properties for the two-dimensional planar Ising model on square lattices. Studying ground-state properties of Ising spin glasses has a long history in the field of theoretical physics. But this research was, and still is, strongly limited due to the complexity of the problem. Although there exists a polynomial time algorithm for the two-dimensional planar case, up to now only for small instances accurate ground states could be determined in an acceptable time. | |||
Contact: |
Title: | Exact Ground States of Hard Ising Spin Glass Instances | |||
Abstract: | The physics of spin glasses (e.g. the alloy CuMn) is not yet fully understood. We determine exact ground states of hard Ising spin glass instances with a branch and cut algorithm and interprete the physics results. | |||
Contact: | ||||
Partners: | Colleagues from the spin-glass community |
Title: | ||||
Abstract: | The maximum cut problem is a prominent NP-hard problem from combinatorial optimization. It is equivalent to optimizing a quadratic objective function over binary variables. We solve it with a branch and cut algorithm that is especially suited for sparse instances. We focus on, but are not limited to, determining maximum cuts in graphs coming from hard Ising spin glass problems that are, e.g., defined on two- or three-dimensional lattices. | |||
Contact: |
Title: | The Maximum k-Cut Problem - Potts Glasses | |||
Abstract: | The maximum k-cut problem asks for 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. Ground states of Potts glasses with k states can be determined by computing a maximum k-cut. We design and implement an exact branch-and-cut algorithm based on semidefinite programming and cutting planes. | |||
Contact: | ||||
Partners: | Miguel Anjos and Bissan Ghaddar, University of Waterloo, Canada |
Title: | q-state Potts model for large q | |||
Abstract: | The partition function of the q-state Potts model with random ferromagnetic couplings and large q amounts to minimizing a particular submodular function. Combinatorial optimization algorithms with polynomial running time exist for minimizing a general submodular function. However, in practice the running time of these algorithms grows strongly with the system size. Thus only relatively small instances can be computed. | |||
Contact: | ||||
Partners: |
Title: | ||||
Abstract: | You need to know exact ground states for your samples? We compute them for you: You submit your short- or long - range samples to the server. You can do this either via a web interface or with a command-line client. Big job batches are possible as well. The results are returned to you via E-Mail. | |||
Contact: | ||||
Partners: |
Title: | ||||
Abstract: | Please follow the link above for information about this project. | |||
Contact: | ||||
Partners: |