Research > 

Current 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 spin 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 design of exact algorithms that always generate correct solutions. A variety of our implementations can be publicly used via the spin glass ground-state server.

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.

Please find here our ongoing projects at a glance.




Title:

Equicut Problem - Coulomb Glasses

Abstract:

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 in which we exploit the close connection to the maximum cut problem. In order to improve the solution approach, we apply problem-specific knowledge and algorithm engineering concepts.

Contact:

A. Schmutzer, F. Liers, G. Pardella

Partners:

M. Anjos




Title:

Exact Algorithms for Robust Network Design with a Set of Traffic Matrices

Abstract:

A crucial issue for the design of modern communication networks is robustness with respect to traffic fluctuations, since they often lead to congestion and traffic bottlenecks. In this project, we address an NP-hard single commodity robust network design problem, where the traffic demands change over time. For different times of the day, we are given for each node the amount of single-commodity flow it wants to send or to receive. The task is to determine the minimum-cost edge capacities such that the flow can be routed integrally through the net at all times. We develop exact branch-and-cut algorithms for its solution and show that they work well on realistic instances.

Contact:

F. Liers

Partners:




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:

F. Liers

Partners:

Colleagues from the spin-glass community



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. We designed a fast polynomial-time algorithm that allows the computation of large planar Ising spin glass instances (up to grid graphs of size 30002) in reasonable time. The implementation is available via the spin glass ground-state server.

Contact:

G. Pardella, F. Liers



Title:

Maximum Cut Problem

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:

F. Liers



Title:

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:

F. Liers

Partners:

M. Anjos, B. Ghaddar, A. Wiegele




Title:

Nonlinear Integer Optimization over Well-Studied Polytopes

Abstract:

The problem of optimizing a nonlinear objective function over integer variables subject to linear constraints arises in many applications. However, it is much harder to solve than integer linear programs in general. Previous approaches are either restricted to very special problems or can only solve small instances. In the project, we focus on nonlinear integer problems that could be solved efficiently for linear objectives. Furthermore, the structure of the feasible solutions is known. Quadratic objectives are a prominent special case. The quadratic assignment problem, the quadratic linear ordering problem and the quadratic matching problem are examples for problems in this class. Starting from a linearization of the nonlinear problem version, we aim at developing general cutting plane approaches leading to improved branch-and-cut algorithms.

Contact:

F. Liers

Partners:

C. Buchheim



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. Only small instances can be computed because the running time of these algorithms grows strongly with the system size.
In our case, faster specialized algorithms can be used. We investigate several approaches to further improve these algorithms in order to reach better average running times.

Contact:

F. Liers

Partners:



Title:

Spin Glass Ground-State Server

Abstract:

You need to know exact ground states for your samples? We compute them for you! Submit your short- or long- range samples to the server using either the web interface or the user-friendly command-line client. Big job batches are possible as well. The results are returned to you via e-mail.

Contact:

F. Liers

Partners:




Title:

Two-layer via minimization in VLSI chip design

Abstract:

Many challenging mathematical optimization problems abound in the design of very large scale integrated (VLSI) chips. One of them consists in assigning the layers to net segments. For connected metalized nets, a layer change is accomplished by a vertical interconnection access (via). Minimizing the number of vias plays a crucial role in the routing step as they not only reduce the electrical reliability and performance of the chip, but also substantially decrease the manufacturing yield. Although the problem is NP-hard in the general case, it is known that the two layer via minimization problem can be solved in polynomial time. Using this approach, we take two adjacent wiring layers from the roughly two dozen present in real-world chips. We integrate practically relevant design rule constraints at the expense of potentially using further vias. We show that often a considerable amount of vias can be saved in a realistic setting. Furthermore, the running times of our method are very small.

Contact:

G. Pardella F. Liers

Partners:

T. Nieberg



Title:

Wiki of COPhy

Abstract:

In this wiki, we introduce the basic concepts of the combinatorial optimization methods that we use in our Combinatorial Optimization in Physics project (COPhy).

Contact:

COPhy