Wir beschäftigen uns mit der Entwicklung, theoretischen Fundierung und numerischen Validierung von Algorithmen zur Lösung von mathematischen Optimierungsproblemen. Dabei betrachten wir verschiedenste Problemklassen: von gemischt-ganzzahliger Optimierung, nichtlinearer und robuster Optimierung bis zur globalen und multikriteriellen Optimierung. Ein besonderer Schwerpunkt liegt auf Optimierungsproblemen, in denen quadratische Funktionen mit Ganzzahligkeitsbedingungen kombiniert werden.

Kombinatorische und Diskrete Optimierung

In der kombinatorischen Optimierung beschäftigt man sich mit Lösungsverfahren für Probleme, die in der Regel eine problemspezifische kombinatorische Struktur der Lösungsmenge aufweisen. Ein klassisches Beispiel ist das Kürzeste Wege Problem. Hier ist ein Graph gegeben und die Lösungsmenge ist implizit durch die Menge von Wegen, die einen vorgegeben Startknoten mit einem Endknoten verbinden, beschrieben. Häufig sind die jeweiligen Optimierungsprobleme durch eine konkrete Anwendung aus der Praxis motiviert.

In der Arbeitsgruppe forschen wir sowohl an exakten, als auch an approximativen Verfahren, die in Polynomialzeit optimale Lösungen bzw. solche mit einer garantierten Güte berechnen.

Algorithmische Spieltheorie

Die nichtkooperative und kooperative Spieltheorie bieten mathematische Beschreibungen von dezentral organisierten Systemen an (z.B. Verkehrssysteme und das Internet); ein fundamentales Konzept der nichtkooperativen Spieltheorie ist z.B. das sogenannte Nashgleichgewicht. Ein zentraler Forschungsschwerpunkt der Arbeitsgruppe ist eine algorithmische Sicht auf die Themenkomplexe Existenz von Gleichgewichten, Berechnungskomplexität von Gleichgewichten und Qualität von Gleichgewichten

Bilevel Optimierung

Eine Optimierung von Systemen, die durch Gleichgewichtsbedingungen charakterisiert sind, fällt in das Gebiet der bilevel Optimierung. Probleme dieser Klasse sind recht schwierig zu lösen, da sie in der Regel nicht-konvex und auch nicht-differenzierbar sind. In diesem Bereich wird an den Themen Optimales Netzwerkdesign unter Gleichgewichtsbedingungen, Design von kombinatorischen Auktionen und Design von optimalen Kostenverteilungen in Netzwerken gearbeitet. Insbesondere wird in der Arbeitsgruppe an der Optimierung von Ampelschaltungen, dem Einsatz von Navigationsgeräten und an einer optimalen Netzplanung (unter Berücksichtigung von Nutzergleichgewichten) gearbeitet.

Codierungstheorie

Die Codierungstheorie dient zur fehlerfreien Übertragung von Daten über gestörte Kanäle. Es handelt sich um ein Teilgebiet der Diskreten Mathematik, das aus den Anwendungen heraus motiviert und entstanden ist; konkrete Anwendungen sind beispielsweise Prüfziffersysteme (ISBN-Nummern etc.), die Datenübertragung in Computernetzwerken oder von Satelliten sowie die Fehlerkorrektur beim CD-Player. 

Angewandte Algebra

Das konkrete Rechnen in Endlichen Körpern spielt für die Anwendungen eine große Rolle (Kryptographie, Codierungstheorie, Signalverarbeitung). Es hat sich herausgestellt, daß dies nur mit Hilfe einer gründlichen Kenntnis der Struktur Endlicher Körper (z.B. Basisdarstellungen) möglich ist. Ein interessantes Anwendungsbeispiel ist die Konstruktion von Folgen mit guten Korrelationseigenschaften, die eng mit den Differenzmengen aus der Design-Theorie zusammenhängen.

Kombinatorische Optimierung, Entwicklung und Analyse von Heuristiken

Es handelt sich um die Behandlung von Optimierungsproblemen durch diskrete Modelle (etwa Graphen und Netzwerke) sowie den Entwurf entsprechender Algorithmen und Heuristiken. Es werden insbesondere für die Praxis relevante Probleme untersucht (Rundreiseprobleme, Matching- und Flusstheorie, Packungsprobleme).

Ganzzahlige Optimierung

Die (lineare gemischt-) ganzzahlige Optimierung bietet die Grundlage zur Modellierung vieler ange-wandter Pro¬bleme der kombinatorischen Optimierung, wie etwa Transport-, Zuordnungs- oder Reihenfolgeprobleme. In den letzten Jahren hat sich die Forschung zusätzlich auf vielerlei theoretische Ansätze zur strukturellen Beschreibung ganzzahliger Programme konzentriert, wie Gröbner-Basen und Testmengen, Basisreduktion in Gittern, Erzeugende Funktionen für das Abzählen von ganzzahligen Punkten in Polytopen.