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.