The Discrete Optimization Research Group

People

Andreas Karrenbauer
Group leader

Ruben Becker
Network Flow

Davis Issac
Biclique Problems

Maximilian John
Quadratic Assignment

Research mission

Discrete optimization problems are ubiquitous. Whenever there is a choice between several possibilities, there is an inherent optimization problem. Our core competence in this area is to recognize such optimization problems, to establish mathematical models, to tackle them by state-of-the-art methods, and to invent new techniques to obtain satisfactory results. Our research is application-driven. This also includes inter-disciplinary research with collaborators from engineering, physics, chemistry, biology, economics, etc.

Network Flow: Some of the most important polynomial time solvable combinatorial optimization problems can be modeled as network flow problems. We investigate different network flow problems, such as the max-flow problem, the min-cost flow problem and others. We are interested in distributed as well as centralized methods for this problem. The current state of the art concerning algorithms for flow problems is somewhat unsatisfactory from a theoretician's point of view: There are algorithms, usually combinatorial algorithms, that are super fast in practice on graphs with millions of nodes and edges. However, the proven run-time bounds for these methods lack behind the nowadays theoretically fastest methods, mostly interior point methods. In our work, we attempt to reduce the described gap.
Biclique Problems: We work on biclique related problems such as Maximum Biclique, Minimum Biclique Cover, Minimum Biclique Partition etc. These problems occur naturally in many applications in a variety of fields like display optimization, data clustering, automata minimization, etc. These problems are all NP-hard and we look at the polynomial time approximability as well as the parameterized complexity of these problems. As far as approximation is concerned, these problems fall into the same ballpark as coloring and independent set which have strong polynomial-time inapproximability (polynomially bad). For the Maximum Biclique Problem, there is still a huge gap between the best known upper and lower bounds on the approximation factor possible in polynomial time which is intriguing. For Biclique Cover and Partition problems, the best known approximation algorithms are very trivial and give very weak approximation factor. It is interesting whether one can get improvements in approximation factor (improvement only by sub-polynomial factors is possible) by cleverer algorithms. We also investigate other problems that fall into this ballpark of strong inapproximability, for eg., the densest-subgraph problem. There are interesting open questions also regarding the parameterized complexity of these problems such as whether the Maximum Biclique admits an FPT algorithm.
Quadratic Assignment: The quadratic assignment problem (QAP) is one of the hardest combinatorial optimization problems. Its range of applications is wide, including facility location, keyboard layout, and various other domains. The key success factor of specialized branch-and-bound frameworks for minimizing QAPs is an efficient implementation of a strong lower bound. We are working on lower bound techniques that are based on the idea of semidefinite programming (SDP). SDP relaxations of the QAP are shown to be very useful in terms of both efficiency and effectiveness. We investigate if and how we can transfer state-of-the-art SDP approaches to the QAP. However, it seems to be unreasonable to solve large-scale quadratic programs to optimality due to its overwhelming complexity. Therefore, approximate solutions are mandatory in many situations. One way of getting good approximate solutions is the application of primal heuristics in a branch-and-bound framework. The advantage is that the duality gap between the approximate solution and the best lower bound in your framework provides a proof of quality for every candidate solution. We are working on new primal techniques based on the SDP approach introduced before. Finally, we plan to extend our techniques to other quadratic problems in order to open the doors to various other applications such as image processing for example.

Projects and positions

Currently, the following projects have project pages, where you can find more information.

Selected Publications