April 25, 2014 Phd students

Binary quadratic problems arise for example in theoretical physics when looking into disordered materials. The Coulomb glass is a model for a disordered material, where the electrons are localized to impurity sites and the electrons strongly interact with each other. We try to find the ground state of these materials.

The ground state is the electron configuration with the lowest total energy. The problems are NP-hard and large instances are very difficult to solve to optimality. Using heuristic methods good solutions are found rather fast but the optimality can not be guaranteed. My research is about finding methods to tackle these kinds of problems.

One method used to get a good lower bound for the problems is semidefinite programming. Some of the problems (the taixxc problems) found in the QAPLIB are very similar to the Coulomb-glass problem and the same techniques can be used on these problems as well. Even though the taixxc problems are very small they are very hard to solve using mixed integer quadratic optimization.