We are always looking for enthusiastic young people who are interested in a research project or thesis in the Bachelor, Master, and PhD programs. There are often topics available that are not listed here, so please contact us if you are interested in a project or thesis within an area of our group's research.

Hybrid Optimization Approaches for Combinatorial Optimization

Date: continuously offered
Topics for: Master/bachelor theses, projects
Contact: Günther Raidl

Many practical combinatorial optimization problems are NP-hard and challenging to solve in practice. While, for example, state-of-the-art mixed integer programming and constrained programming solvers are powerful tools to effectively solve small to medium sized instances of such problems to proven optimality, they frequently do not scale well enough to larger problem instances. Heuristiscs and metaheuristics, such as local search, variable neighborhood search, tabu search, or evolutionary approaches, are frequently applied in these cases as viable alternatives, although they usually do not provide quality guarantees.

In our research we try to utilize and combine the best of such different techniques with the aim of coming up with hybrid solution approaches that are able to outperform traditional methods in terms of the quality of heuristic solutions or the time in which they are obtained. Such hybrids may be of pure heuristic nature, possibly additionally provide quality guarantees, or can be so-called anytime-algorithms which provide promising heuristic solutions very soon but are also guaranteed to finally terminate with a proven optimal solution given enough time. Large neighborhood search approaches or tree-search methods guided by strong heuristics are prominent examples for hybrid optimization approaches.

In our recent research, we in particular consider machine learning techniques for learning functions that guide (hybrid) optimization techniques for improved performance.

Considered problems come from many different areas including scheduling, transport optimization, E-mobility, network design, graph theory, bioninformatics, quantum computing, and cutting and packing.

Requirements:

• Proficiency in algorithmics
• Interest in heuristic optimization techniques, mathematical programming, constrained programming and/or machine learning
• Good programming skills

Solving Hard Combinatorial Problems with SAT and QBF Solvers

Over the last two decades, SAT-solvers (which are programs that solve the Boolean satisfiability problem) have become surprisingly powerful and can check the satisfiability of instances with hundreds of thousands of variables in a few minutes. Among the most powerful SAT-solvers are Glucose and Lingeling.The subject for a Bachelor or Masters thesis would be to translate a hard combinatorial problem into SAT and solve it with a SAT-solver. For such a translation (often called encoding) there are usually many different approaches, and part of the thesis would be to compare different approaches experimentally on a set of problem instances.

The considered combinatorial problem can be chosen from a large pool of problems, including graph, clustering and optimization problems. Some recent research in this direction can be found here and here.

For even harder problems, like finding a winning strategy for a board game, one needs to go beyond SAT and use a QBF solver (Qute is such a solver we developed in our group).

Date: February 2018
Topic for: Bachelor/Master Theses
Contact: Stefan Szeider

Graph Drawing

Date: topics continuously available
Topic for: Bachelor/Master Theses
Contact: Martin Nöllenburg

Graph Drawing is concerned with algorithms to compute geometric representations of graphs and networks. Applications of graph drawing range from graph visualizations for human users to hardware layouts and wireless routing. Scientifically, the area offers a wide spectrum of topics for student theses, from theoretical questions (e.g., existence of certain layouts or algorithms with certain properties) to practical questions of modeling the actual requirements of a particular application and designing, implementing, and evaluating algorithms for solving it.

Requirements:

• Proficiency in (graph) algorithmics
• Interest in geometry and visualization
• Practical topics: good programming skills

Algorithmic Cartography and Geometry

Date: topics continuously available
Topic for: Bachelor/Master Theses
Contact: Martin Nöllenburg

Digital cartography offers a wide spectrum of visualization problems that can be solved by geometric algorithms. The types of maps range from dynamic and interactive maps, e.g., on smart phones and mobile devices, to unconventional diagrammatic or schematic maps. Examples of algorithmic problems comprise label placement for map features, algorithms for constructing cartograms, or schematic destination maps. The area contains both topics with a stronger practical focus (including evaluation) or with a more theoretical focus. Thesis topics in computational geometry without direct links to cartography are also possible.

Requirements:

• Proficiency in algorithmics and geometric algorithms
• Interest in maps and interdisciplinary work
• Practical topics: good programming skills