Our group works in the areas of discrete applied mathematics, operations research and mathematical optimization. Having a strong theoretical focus the research is often based on real world applications and has strong ties with theoretical computer science and engineering disciplines.
Our methods are taken from a variety of fields such as:
- integer and combinatorial optimization
- network flow and graph theory
- multicriteria optimization
- algorithmic game theory
- online optimization
- scheduling and location theory
What is optimization?
Discrete optimization is a branch of applied, discrete mathematics. Within discrete optimization, we distinguish between combinatorial optimization problems and (mixed) integer (linear) optimization problems.
Combinatorial optimization analyzes structural properties of a countable set of elements and uses them as best as possible to maximize or minimize objective functions on that set. Examples of discrete optimization problems we are exploring are scheduling problems, knapsack problems, graph editing problems, or matchings. We also deal with variants of classical formulations, e.g. generalized bottlenek objective functions or multiple conflicting objective functions. Very often, the problems we look at are difficult and we therefore investigate - in addition to exact solution methods - also approximations.
In integer optimization, we are looking for integer solutions in a (high-dimensional) polyhedral domain that maximize or minimize a given linear objective function. Integer models appear in totally different applications. In particular, we are concerned, e.g. with the question of how in digital communication the maximum likelihood decoding problem can be solved by methods of integer optimization. Thus, we provide reference results for the development of heuristic methods, e.g. currently used in mobile communications.
Graphs and Networks
Mathematics deals with abstract structures and such a structure that we often consider are so-called graphs. In its simplest form, a mathematical graph consists of a set of objects (nodes) and links between them (edges). Using graphs, we then model in applications, e.g. Road networks, electrical circuits or social networks. If one adds data to mathematical graphs such as the properties of edges (lengths, costs, capacities, ...), one actually speaks of mathematical networks.
Through these structures, we solve a whole range of different optimization problems in the disciplines of location planning, network flows, digital communication, or supply chain management. Specifically, we are currently working among other topics on simplifying Tanner graphs, on edge-cover problems, on dynamic network flow problems, or on results for graphs with a limited tree-size.
In addition to the structural-mathematical analysis and the complexity-theoretical classification of graph-theoretic or network-based optimization problems, another important component of our work is the design and implementation of efficient algorithms. Depending on the problem class, we strive for exact or approximate algorithms or schemas with the lowest possible (worst-case) runtimes. Often we also implement these algorithms and thus actually solve real problems.
Modelling real-world problems often requires optimizing several conflicting objectives simultaneously, even for very simple problems like buying a car: Minimizing cost while maximizing engine performance usually cannot be achieved by one solution. Hence, some trade-off solution or compromise has to be found. Multicriteria Optimization (aka. Multiobjective Optimization or Vector Optimization) is dedicated to the task of solving optimization problems with more than one objective function. As one cannot hope for having only one optimal solution, this is achieved by returning several trade-off solutions, also known as Pareto optimal solutions.
This topic has a widespread field of applications, such as production planning, portfolio management, controlling, process optimization, environment protection, location planning, civil security and many more. Hence, this topic is not only of interest for mathematicians but also plays a role in the fields of economics and computer science. There are different approaches: finding all Pareto optimal solutions, using a preference function or using a decision maker that is interactively involved in the solution process.
As research in this field is in the early stages, we aim to advance research in Multicriteria Optimization from both a theoretical and practical point of view with fundamental research and real-world problems.
Our theoretical investigations in the field of optimization are mainly motivated by applications from various fields.
Current applications include, for example, questions of strategically favorable spatial positioning in emergency rescue and optimization of outpatient medical care, as well as many applications from transportation planning, such as route planning in rail networks, the optimal creation of lines, timetables and circulation plans in public transport, or developing efficient tariff systems. Some applications in the past were the planning of demonstrations and protest marches, the optimization of house insulation, the creation of shift plans in hospitals and the support of large-scale evacuations. Interestingly, many challenges arising from these different application areas can be reduced to related mathematical concepts. In particular, we are interested in new challenges and are available as a contact person for technical and economical problems.
Our motivation is driven by applications, since within the scope of real-world issues one immediately gets to know about the value of applied mathematics. We like to pass on this motivation to students by integrating them within practical oriented projects, e.g., internships, student assistant jobs and final paper. Further, applications are of course also suitable for communicating the importance of modern mathematics to students and teachers — this is another task that we are eager to pursue in a number of ways.