Embed Size (px)
Citation preview
Lehrstuhl für Diskrete Mathematik, Optimierung und Operations Research
Prof. Dr. Dieter Jungnickel
Prof. Dr. Tobias Harks (seit Oktober 2015)
apl. Prof. Dr. Dirk Hachenberger
Jahresbericht 2015
Prof. Dr. Dieter Jungnickel Prof. Dr. Tobias Harks apl. Prof. Dr. Dirk Hachenberger
Universitätsstr. 14
86159 Augsburg
Telefon +49 (0) 821 598 - 2214
Telefon +49 (0) 821 598 - 2234
Telefon +49 (0) 821 598 - 2216
Telefax +49 (0) 821 598 - 2772
www.math.uni-augsburg.de/prof/opt/
1. Arbeitsgebiete des Lehrstuhls
Codes und Designs (Jungnickel)
Es gibt enge Zusammenhänge zwischen Codierungs- und Designtheorie: Designs liefern häufig
(auch praktisch relevante) Codes, während andererseits interessante Designs oft über Codes
konstruiert werden. Das Studium des Codes eines Designs ist jedenfalls ein wesentliches Hilfs-
mittel, um die Struktur des Designs besser zu verstehen. In diesem Zusammenhang ist bei-
spielsweise die berühmte Hamada-Vermutung zu nennen, die versucht, die klassischen geomet-
rischen Designs über den p-Rang ihrer Codes zu charakterisieren. Zusammen mit V.D. Tonchev
sind vor kurzem die ersten unendlichen Serien von Gegenbeispielen zu dieser Vermutung konstru-
iert worden; andererseits wurde eine modifizierte codierungstheoretische Charakterisierung
erreicht. Darauf aufbauend wurde eine allgemeine Theorie entwickelt, die unerwartet enge Bezüge
zwischen einfachen Inzidenzstrukturen, Codes und Galois-Geometrien aufzeigt.
Design-Theorie (Jungnickel)
Die Design-Theorie beschäftigt sich mit der Existenz und Charakterisierung von Blockplänen, t-
Designs, lateinischen Quadraten und ähnlichen Strukturen. Wichtig ist auch die Untersuchung der
zugehörigen Automorphismengruppen und Codes. Am Lehrstuhl wird insbesondere die Theorie
der Differenzmengen eingehend untersucht. Dieses Gebiet hat Anwendungen z.B. in der
Versuchsplanung, Signalverarbeitung, Kryptographie sowie in der Informatik.
Endliche Geometrie (Jungnickel)
Einer der wesentlichen Teilbereiche der endlichen Geometrie ist das Studium endlicher projektiver
Ebenen. Ein herausragendes Problem ist dabei die Primzahlpotenzvermutung (PPC), derzufolge
jede endliche projektive Ebene als Ordnung eine Primzahlpotenz hat. Man versucht, diese PPC
wenigstens für den Fall interessanter Kollineationsgruppen nachzuweisen, insbesondere für
Ebenen mit quasi-regulären Gruppen, wie sie in der Dembowski-Piper-Klassifikation auftreten. In
den letzten Jahren ist dieser Nachweis am Lehrstuhl für zwei bislang offene Fälle gelungen. Die
noch übrigen Fälle werden weiterhin untersucht.
Kombinatorische und Diskrete Optimierung (Harks)
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. Im Folgenden sind einige solche
Problemklassen aufgeführt:
Routing-, und Scheduling-Probleme mit Anwendungen im Verkehr, Telekommunikation und
Logistik
Standortplanung in der Logistik
mehrdimensionale Packungsprobleme in der Logistik
Tarifoptimierung in der Transportplanung
Matching Probleme mit Budget Schranken und ihre Anwendungen in Wireless Networks
Matroid Theorie mit Anwendungen im Netzwerkdesign
Polymatroid Theorie mit Anwendungen im Verkehr
LP/IP basierte exakte Verfahren
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 (Harks)
In der klassischen Optimierung wird angenommen dass alle Entscheidungsvariablen zentral
bestimmt werden können. Einige praxisrelevante Systeme (wie z.B. Verkehrssysteme und das
Internet) sind jedoch dezentral organisiert und können somit nur indirekt gesteuert werden. Die
nichtkooperative und kooperative Spieltheorie bieten mathematische Beschreibungen von solch
dezentral organisierten Systemen an; ein fundamentales Konzept der nichtkooperativen
Spieltheorie ist z.B. das sogenannte Nashgleichgewicht. Ein zentraler Forschungsschwerpunkt der
Arbeitsgruppe ist eine algorithmische Sicht auf folgende Themenkomplexe:
Existenz von Gleichgewichten
Berechnungskomplexität von Gleichgewichten
Qualität von Gleichgewichten
Bilevel Optimierung (Harks)
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
folgenden Themen gearbeitet:
Optimales Netzwerkdesign unter Gleichgewichtsbedingungen
Design von kombinatorischen Auktionen
Design von optimalen Kostenverteilungen in Netzwerken
Die algorithmische Theorie der Optimierung unter Gleichgewichtsrestriktionen ergibt interessante
Anwendungsmöglichkeiten, z.B. im Bereich der Optimierung von Verkehrssystemen. 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 (Hachenberger, Jungnickel)
Die Codierungstheorie dient zur fehlerfreien Übertragung von Daten über gestörte Kanäle. Es
handelt sich um ein Teilgebiet der Diskreten Mathematik; konkrete Anwendungen sind beispiels-
weise Prüfziffersysteme (ISBN-Nummern etc.), die Datenübertragung in Computernetzwerken
oder von Satelliten sowie die Fehlerkorrektur beim CD-Player.
Angewandte Algebra, insbesondere Endliche Körper (Hachenberger, Jungnickel)
Das konkrete Rechnen in Endlichen Körpern spielt für die Anwendungen eine große Rolle (Krypto-
graphie, Codierungstheorie, Signalverarbeitung). Es hat sich herausgestellt, dass dies nur mit Hilfe
einer gründlichen Kenntnis der Struktur Endlicher Körper (z.B. Basisdarstellungen) möglich ist. In
diesem Zusammenhang ist die Existenz von Normalbasen mit gewissen zusätzlichen
Eigenschaften von Interesse. Ein interessantes Anwendungsbeispiel ist die Konstruktion von Fol-
gen mit guten Korrelationseigenschaften, die eng mit den Differenzmengen aus der Design-Theorie
zusammenhängen.
Kombinatorische Optimierung, Entwicklung und Analyse von Heuristiken (Hachenberger, Jungnickel)
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 (Hachenberger)
Die (lineare gemischt-) ganzzahlige Optimierung bietet die Grundlage zur Modellierung vieler ange-
wandter Probleme 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.
2. Mitarbeiter
Monika Deininger (Sekretärin)
Anja Huber, M.sc. Wissenschaftliche Mitarbeiterin
Manuel Surek, M.sc. Wissenschaftlicher Mitarbeiter
3. Abschlussarbeiten
Diplomarbeiten
Mischok, Julius: Decodierung von Reed-Solomon-Codes
Erstgutachter: Prof. Jungnickel, Zweitgutachter: Prof. Hachenberger
Die Codierungstheorie ist die mathematische Grundlage für einige der erfolgreichsten Anwen-
dungen der (diskreten) Algebra in unserem von Elektronik und Digitalisierung zunehmend
geprägten Alltag. Codes dienen dazu, bei der Übertragung von Nachrichten über gestörte Kanäle
(beispielsweise Telefonleitungen, Computer-Netzwerke oder Funkverbindungen) wie bei der
Speicherung von Daten (auf Medien wie CDs, DVDs und Blu-Rays ebenso wie bei Artikelnum-
mern) auftretende Fehler zu korrigieren (und so die eigentlichen Daten aus der fehlerhaft vorlie-
genden Information zu rekonstruieren) oder aber zumindest zu entdecken (und dann beispiels-
weise eine nochmalige Übertragung der Nachricht zu verlangen).
Dabei beruhen die erwähnten Anwendungen für CDs und ähnliche Speichermedien auf den Reed-
Solomon-Codes, die auch theoretisch von besonderem Interesse sind, da sie die bekannte
Singletonschranke mit Gleichheit erfüllen und somit optimale Fehlerkorrektureigenschaften haben:
Es handelt sich hier um die klassischen Beispiele für die sogenannten MDS-Codes. Für eine
gegebene Primzahlpotenz q , eine gegebene Codelänge n£ q-1 und jedes d mit 1£ d £ n ist der
Reed-Solomon-Code RS(q,d,n) ein d -dimensionaler linearer Code über dem endlichen Körper
GF(q) mit q Elementen, der Minimalabstand n-d+1 hat und somit bis zu e:=n- d
2
ê
ëêú
ûú Fehler
korrigieren kann. Sowohl die Codierung wie die Decodierung können dabei effektiv (also in
polynomialer Zeit) vorgenommen werden; für die Codierung ist das trivial, und für die Decodierung
kann man beispielsweise den Berlekamp-Welch-Algorithmus verwenden.
Wenn mehr Fehler aufgetreten sind, ist im allgemeinen keine eindeutige Decodierung möglich. In
einer fundamentalen Arbeit aus dem Jahre 1997 hat Madhu Sudan ein polynomiales Verfahren
angegeben, das trotzdem eine Art Decodierung jenseits der Singleton-Schranke ermöglicht, wobei
die Ausgabe allerdings kein eindeutiges (korrigiertes) Codewort ist, sondern eine Liste möglicher
Codeworte (List-Decoding). Da die Einzelheiten technisch kompliziert sind, sei hier nur das Fazit
von Sudans Resultaten erwähnt: Wenn der verwendete Code eine niedrige Informationsrate hat,
kann der Algorithmus mit einer relativ hohen Fehlerzahl umgehen. Beispielsweise erlaubt die
Singleton-Schranke es, bei einer Informationsrate von 0,1 mittels des Berlekamp-Welch-
Algorithmus bis zu einer Fehlerrate von 0,45 zu decodieren, während das Verfahren von Sudan
zur Listendecodierung bis zu einer Fehlerrate von 0,602 greift und dabei eine Liste von maximal 4
möglichen Codewörtern liefert.
Herr Mischok hat in seiner Arbeit die eben beschriebenen Fragestellungen detailliert dargestellt
und insbesondere die Korrektheit des Berlekamp-Welch-Algorithmus sowie des Verfahrens von
Sudan gezeigt; darüber hinaus wurden beide Algorithmen in Java implementiert.
Masterarbeiten
Bläßing Christian: Gröbnerbasen und Graverbasen im Kontext zur ganzzahligen Linearen
Optimierung
Erstgutachter: Prof. Hachenberger, Zweitgutachter: Prof. Jungnickel
Die in der Praxis üblicherweise verwendeten Verfahren zur Lösung von linearen ganzzahligen
Optimierungsproblemen sind dualer Natur und beruhen auf Schnittebenen- und Branch and
Bound-Strategien. Ausgehend von den Pionierleistungen von Graver (1975), sowie Conti und
Traverso (1991) rückten in den letzten Jahren aber auch primale, auf sog. Testmengen beruhende
Verfahren in das Blickfeld der ganzzahligen Optimierung.
Die Grunddaten bestehen aus einer Restriktionsmatrix und einem Zielfunktionsvektor; diese legen
eine Familie ganzzahliger linearer Programme in Standardform mit variierender rechter Seite fest.
Eine zugehörige Testmenge besteht aus einer endlichen Menge von potentiellen Ver-
besserungsrichtungen mit denen man einen zulässigen Punkt schrittweise (diskret) zu einem
Optimum führen kann.
Im Gegensatz zu diesem erstaunlich einfachen Optimierungsprinzip geht in die Bestimmung von
Testmengen (deren Existenz stets gewährleistet ist) eine ganze Bandbreite interessanter und
komplexer Mathematik ein. Die konkrete Berechnung von Testmengen kann allerdings sinnvoll-
erweise nur mit Computereinsatz bewerkstelligt werden, zumal die Mächtigkeit einer solchen
Menge sehr groß sein kann. Das von Hemmecke, Köppe, Malkin und Walter entwickelte, frei
verfügbare Programmpaket 4ti2 (www.4ti2.de) beinhaltet zweifellos die beste Implementierung zur
Berechnung von Testmengen.
Die Hauptaufgabe von Herrn Bläßing bestand in der Ausarbeitung eines Artikels von Hemmecke
und Malkin (2006), in dem die theoretischen Grundlagen der in 4ti2 verwendeten Algorithmen
erläutert werden. Die breit eingestreuten, selbst gewählten Beispiele sowie die erläuternden
Graphiken tragen sehr zum Verständnis der technischen Argumente bei. Herr Bläßing stellt auch
einige theoretische Grundlagen zu sog. universellen Testmengen dar — hierbei wird neben der
rechten Seite auch die Zielfunktion variiert.
Netzsch Stephanie (geb. Gleich): Das Problem des chinesischen Postboten
Erstgutachter: Prof. Jungnickel, Zweitgutachter: Prof. Hachenberger
Das Chinese Postman Problem (oder kurz CPP) ist eines der bekannteren Probleme der Kombi-
natorischen Optimierung. Anschaulich gesprochen geht es um einen Postboten, der eine möglichst
günstige Route zur Zustellung seiner Post finden möchte. Formal betrachtet man eine positive Gewichtsfunktion w auf den Kanten eines zusammenhängenden Graphen G, der den Zustell-
bezirk unseres Postboten modelliert; dabei kann man w als Straßenlänge oder erwarteten
Zeitbedarf interpretieren. (Andere Anwendungen des CPP sind beispielsweise die Routenplanung
für die Müllabfuhr oder für den Winterdienst.) Man sucht dann eine Postbotentour - also einen geschlossenen Kantenzug, der jede Kante von G mindestens einmal enthält - mit möglichst
geringem Gesamtgewicht. Wenn G Eulersch ist, ist die Lösung einfach durch eine Eulertour
gegeben; andernfalls muss man geeignete Menge M von Kanten von G verdoppeln, um aus G
einen Eulerschen Multigraphen zu erhalten, wobei M natürlich möglichst geringes Gewicht haben
soll.
Man muss nun unterscheiden, wie man genauer modelliert. So wie eben beschrieben, spielt die
Durchlaufrichtung der Kanten (bzw. Straßen) keine Rolle. Will man aber beispielsweise Einbahn-
straßen berücksichtigen, muss man von Graphen zu Digraphen übergehen (wenn jede Straße in
einer vorgegebenen Richtung zu durchlaufen ist) oder zu gemischten Graphen, bei denen sowohl
Bögen - also gerichtete Kanten - wie (ungerichtete) Kanten auftreten können. Interessanterweise
haben diese drei Varianten einen unterschiedlichen Schwierigkeitsgrad:
Das klassische CPP ist stets lösbar und es gibt verhältnismäßig einfache Verfahren, wie man
eine Lösung mit Komplexität (O V3) bestimmen kann. Dazu muss man nur Eulersche Kreise,
kürzeste Wege und minimale gewichtete Matchings bestimmen können.
Im gerichteten Fall (DCPP) muss nicht immer eine Lösung existieren: Der Zusammenhang von
G reicht nicht mehr aus, man muss G vielmehr als stark zusammenhängend verlangen. Dann
kann man aber wieder (immer noch verhältnismäßig einfach) eine Lösung bestimmen, wobei
man nun entweder die Flusstheorie verwendet (Bestimmung optimaler Flüsse bzw. Lösung von
Transportproblemen) oder mit geeigneten ganzzahligen Linearen Programmen arbeitet. Der
theoretische Background ist jedenfalls anspruchsvoller und die Behandlung des Problems
etwas aufwändiger.
Der allgemeine Fall des CPP auf gemischten Graphen (MCPP) ist der bei weitem schwierigste. Zunächst muss G dann noch eine weitere Voraussetzung (nämlich eine
Balanciertheitsbedingung) erfüllen, damit überhaupt eine Lösung existiert. Zudem ist die Bestimmung einer Lösung unvergleichlich schwieriger, da das MCPP zu den NP-schweren
Problemen gehört, einer Klasse von Problemen, für die vermutlich keine polynomialen Algo-
rithmen existieren.
Frau Netzsch hat in ihrer Masterarbeit eine Übersicht über die drei beschriebenen Varianten
gegeben, wobei sie sowohl theoretische Ergebnisse zur Lösbarkeit wie auch entsprechende
Algorithmen behandelt und für die beiden einfacheren Fälle auch jeweils einen Algorithmus
implementiert hat.
Bachelorarbeiten
Fasching Johannes: Constraint Qualifications und Bedingungen zweiter Ordnung in der nichtli-
nearen Optimierung
Erstgutachter: Prof. Hachenberger, Zweitgutachter: Prof. Jungnickel
Ein zentrales Problem der sog. Nichtlinearen Optimierung besteht in der Minimierung einer (hin-
reichend oft) differenzierbaren reellwertigen Zielfunktion, die auf einem Teilbereich eines endlich-
dimensionalen euklidischen Vektorraums betrachtet wird. Dieser sog. Zulässigkeitsbereich wird
durch jeweils endlich viele glatte Ungleichungs- sowie Gleichungsrestriktionen beschrieben. In der
Theorie geht es um die Formulierung von notwendigen und hinreichenden Bedingungen, die lokale
oder globale Optimalpunkte erfüllen müssen. Zum erweiterten Kandidatenkreis dieser Stellen
gehören die sog. KKT-Punkte; das sind Punkte, für die der negative Zielfunktionsgradient als
Linearkombination dargestellt werden kann, wobei die Lagrange-Multiplikatoren für die
Ungleichungsrestriktionen nicht-negativ sein und die sog. komplementären Schlupfbedingungen
erfüllen müssen.
Die Erzwingung dieser KKT-Eigenschaft benötigt neben der Voraussetzung der lokalen Minimalität
des betrachteten Punktes allerdings noch eine weitere Eigenschaft, eine sog. Constraint
Qualification. Dabei handelt es sich üblicherweise um die Formalisierung einer geometrischen
Eigenschaft, die die Umgebung des Punktes im Verhältnis zum Zulässigkeitsbereich aufweist.
Unter gewissen Konvexitätsannahmen an die beteiligten Funktionen erweist sich die KKT-Eigen-
schaft sogar als global hinreichend. Zusammen mit der Lagrange-Dualität bildet dies mehr oder
weniger den Kanon des nichtlinearen Teils unserer Bachelor-Vorlesung Optimierung II. Auf die
numerische Untersuchung von Iterationsverfahren, die gegen KKT-Punkte konvergieren, kann
nicht eingegangen werden.
Herr Fasching erweitert in seiner Bachelorarbeit die oben erwähnten Vorlesungsinhalte durch
einige wichtige Aspekte. Konkret geht es zum einen darum, weitaus mehr Constraint Qualifications
zu betrachten und diese untereinander in Beziehung zu setzen. Zum anderen wird die Theorie
durch notwendige und hinreichende Bedingungen zweiter Ordnung bereichert. Diese beinhalten
gewisse Definitheitseigenschaften eines Operators, der aus den zum betrachteten Punkt
gehörenden Hesse-Matrizen der beteiligten Funktionen kombiniert wird.
Hick Martin: Zur Lösung und Analyse von linearen Optimierungsproblemen
Erstgutachter: Prof. Hachenberger, Zweitgutachter: Prof. Jungnickel
Die Lösung von Linearen Optimierungsproblemen gehört ohne Zweifel zu den wichtigsten Aufga-
ben der mathematischen Optimierung. Deshalb wird diese Thematik in der Grundausbildung
unserer Bachelorstudiengänge auch gebührend (allerdings nicht erschöpfend) behandelt.
Ausgehend von unseren Bachelor-Vorlesungen zu Optimierungmethoden analysiert und diskutiert
Herr Hick in seiner Bachelorarbeit einige weitere wichtige Facetten der Linearen Optimierung.
Konkret betrachtet Herr Hick die seit ihrer Entdeckung vor etwa 30 Jahren immer populärer
werdenden Inneren-Punkte-Verfahren, wobei der Fokus auf der theoretischen Herleitung des
zentralen Pfads und einigen Grundstrategien bei der Pfadverfolgung liegt.
Ein weiterer Gegenstand der Bachelorarbeit von Herrn Hick ist die für wirtschaftliche Aspekte
wichtige Sensitivitätsanalyse, also die Frage, ob und ggf. wie sich ein Optimalpunkt ändert, wenn
man die rechte Seite oder die Zielfunktion des primalen Problems variiert. Diese wird hier haupt-
sächlich anhand der Theorie der Inneren-Punkte-Verfahren beleuchtet.
Die Arbeit wird durch die Betrachtung (stark) entarteter Probleme abgerundet, wobei insbesondere
eine Verfahrensweise (alternativ zu denen aus der Vorlesung) vorgestellt wird, die die
Terminierung des Simplexverfahrens gewährleistet.
Hoen Alexander: Implementierung und Visualisierung von Verfahren zur Bestimmung des zwei-
fachen Kanten- und Knotenzusammenhangs bei Graphen
Erstgutachter: Prof. Hachenberger, Zweitgutachter: Prof. Jungnickel
Herr Hoen betrachtet mit dem zweifachen Kanten- bzw. Knotenzusammenhang in (ungerichteten)
Graphen eine grundlegende Problemstellung aus der Graphentheorie, die u.a. Anwendungen in
der Analyse von Kommunikationsnetzwerken hat.
Beginnend mit einer Tiefensuche analysiert Herr Hoen zwei unterschiedlich konzeptionierte Algo-
rithmen, die den zweifachen Kanten- bzw. Knotenzusammenhang eines Graphen entscheiden.
Herr Hoen hat diese insgesamt drei Verfahren implementiert und in das Programmpaket VINA
eingebunden. Das Grundkonzept des mittlerweile durch verschiedene Abschlussarbeiten
gewachsenen Programmpakets VINA besteht in einer Visualisierung einzelner Schritte eines
Algorithmus auf einer graphischen Oberfläche, die durch begleitendes Datenmaterial über die
Inhalte von Zustandsvariablen ergänzt werden.
Kraus Georg: Gomory-Hu-Bäume von Netzwerkern: Berechnung und Anwendungen in der
Graphentheorie
Erstgutachter: Prof. Hachenberger, Zweitgutachter: Prof. Jungnickel
Ausgangspunkt für die schwierige Erläuterung des Begriffs Gomory-Hu Baum ist ein vollständiger
Graph auf 𝑛 Knoten, auf dessen Kanten eine nichtnegative Kapazitätsfunktion gegeben ist. Geht
man zur vollständigen Orientierung dieses Graphen über, so stellt sich für je zwei verschiedene
Knoten die Frage nach dem maximalen Flusswert, den ein zulässiger Fluss zwischen diesen
beiden Knoten haben kann. Prinzipiell kann die globale Flussfunktion durch 𝑂(𝑛2) Aufrufe eines
Max-Flow Algorithmus berechnet werden. Andererseits lässt sich eine solche Flussfunktion aber
bereits auf einem minimal zusammenhängenden Netzwerk realisieren, also durch einen Baum mit
𝑛 − 1 Kanten beschreiben (man spricht von einem sog. äquivalenten Flussbaum).
Ein Gomory-Hu Baum (auch Schnittbaum genannt) ist ein spezieller äquivalenter Flussbaum, der
sich durch folgende zusätzliche Eigenschaft auszeichnet: Für jede Kante dieses Baumes bilden
die beiden Komponenten, die nach Entfernen dieser Kante entstehen, einen minimalen Schnitt für
die beiden Endknoten dieser Kante. Das aus der Dualitätstheorie bekannte Max-Flow-Min-Cut
Theorem besagt, dass dieser minimale Schnittwert exakt dem maximalen Flusswert zwischen
diesen beiden Endknoten entspricht. Dies ermöglicht es letztendlich, die globale Flussfunktion
durch lediglich 𝑂(𝑛) Aufrufe eines Max-Flow Algorithmus zu berechnen.
Herr Kraus beschreibt in seiner Bachelorarbeit detailliert zwei Verfahren zur Bestimmung eines
Gomory-Hu Baumes zu einem gegebenen vollständigen Netzwerk (neben dem klassischen von
Gomory und Hu auch ein Neueres von Gusfield aus den 1990-er Jahren). Des weiteren diskutiert
Herr Kraus im Rahmen eines Überblicks fünf weitere (zum Teil harte) Problemstellungen aus der
kombinatorischen Optimierung, zu deren (zumindest approximativen) Lösung die Gomory-Hu
Bäume einen erheblichen Beitrag leisten.
Langer Manuela: Untersuchung des Sport-Eliminations-Problems mit Methoden der Optimierung
Erstgutachter: Prof. Hachenberger, Zweitgutachter: Prof. Jungnickel
Nach dem 18. Spieltag der Fußball Bundesliga Saison 2014/15 stand Borussia Dortmund auf dem
letzten Tabellenplatz. Die natürliche Frage, die alle Fußballinteressierten umtrieb, war: Schafft der
BVB den Klassenerhalt? Optimistischere Betrachter fragten sich, ob diese Mannschaft noch einen
Startplatz für einen internationalen Wettbewerb erreichen kann. Eine eher theoretische
Fragestellung ist, ob Dortmund bei der Konstellation nach dem 18. Spieltag noch hätte Meister
werden können, oder bereits eliminiert war.
In ihrer Bachelorarbeit beschäftigt sich Frau Langer mit dieser kombinatorischen Problemstellung,
die in den letzten Jahren einige Beachtung gefunden hat. Zur formalen ganz allgemein gehaltenen
Problembeschreibung betrachtet man eine Grundmenge von Teams, die eine Meisterschaftsrunde
austragen. Dabei wird nur festgelegt, wie oft zwei verschiedene Mannschaften gegeneinander zu
spielen haben, und nach welchem Muster die Punktevergabe erfolgt. Ein Team, das am Ende die
meisten Punkte hat wird Meister; haben mehrere Teams die meisten Punkte erreicht, so wird unter
diesen die Meisterschaft geteilt bzw. alle sind Meister. Angenommen, die Meisterschaftsrunde ist
zu einem Teil absolviert. Ein Team 𝑡 heißt dann eliminiert, wenn es zu jedem Szenario für den Rest
der Meisterschaft wenigstens ein Team gibt, das unter diesem Szenario echt mehr Punkte erreicht
als 𝑡.
Im einfachsten Modell (keine Unentschieden), das zum Beispiel im amerikanischen Baseball
praktiziert wird, können durch geschickten Einsatz der Flusstheorie alle eliminierten Teams effizient
bestimmt werden. Dabei macht sich die Entscheidung an einem bestimmten Schwellenwert fest.
Ein solcher Schwellenwert existiert auch bei einer allgemeineren Punktevergabe wie sie zum
Beispiel in der Fußball-Bundesliga gehandhabt wird. Allerdings erweist sich dabei das
Eliminationsproblem bereits als NP-schwer, weshalb in diesem Fall leider nicht zu erwarten ist,
dass ein effizientes Verfahren zur Bestimmung aller eliminierten Teams jemals gefunden wird.
Schydlo Ramona: Die Berechnung von Flüssen mit minimalen Kosten mit Hilfe des Netzwerk-
Simplex-Algorithmus
Erstgutachter: Prof. Hachenberger, Zweitgutachter: Prof. Jungnickel
Beim Minimalkostenflussproblem (MCFP) geht es um die Berechnung eines kostenminimalen
Gütertransports bzw. eines optimalen (zulässigen) Flusses innerhalb eines Netzwerkes von An-
bietern zu Abnehmern. Es wird durch gerichtete Graphen mit Kapazitätsschranken und einer
Kostenfunktion auf den Kanten, sowie mit einer Angebots-Nachfrage-Funktion auf den Knoten
modelliert. Zur effektiven Lösung dieses Problems gibt es viele Ansätze, u.a. die in den Vorle-
sungen zur Optimierung behandelten Algorithmen zur Lösung des Max-Flow- sowie des Min-Cost-
Circulation-Problems.
In ihrer Bachelorarbeit betrachtet Frau Schydlo mit dem Netzwerk-Simplex-Algorithmus ein weite-
res, weit verbreitetes Verfahren zur Lösung des MCFP. Dieses stellt eine schöne Verbindung
zwischen der linearen und der kombinatorischen Optimierung dar: Wie bei dem für allgemeine
lineare Programme konzipierten Simplex-Algorithmus besteht die Grundidee darin, zulässige
Basislösungen auf der Grundlage einer Nachbarschaftsbeziehung solange sukzessive lokal zu
verändern, bis eine optimale Basislösung vorliegt. Im vorliegenden graphischen Fall entsprechen
die zulässigen Basislösungen den aufspannenden Bäumen des zugrundeliegenden Digraphen,
und ein Basiswechsel vollzieht sich durch das Auswechseln einer Baumkante mit einer Nicht-
Baumkante unter dem Aspekt einer Kosteneinsparung.
Frau Schydlo stellt detailliert die Arbeitsweise und die Korrektheit des Netzwerk-Simplex-Algo-
rithmus dar. Dabei verdeutlicht Sie anhand eines eigenen Beispiels und durch schöne Graphiken
verschiedene komplexe Details dieses Algorithmus.
Sticker Sebastian: Ein polynomiales Approximationsverfahren für das Euklidische TSP
Erstgutachter: Prof. Jungnickel, Zweitgutachter: Prof. Hachenberger
Das Traveling Salesman Problem (oder kurz TSP) ist eines der wichtigsten Probleme der Kombi-natorischen Optimierung und wird in der einschlägigen Vorlesung als Prototyp eines NP-schweren
Problems behandelt, einer Klasse von Problemen, für die vermutlich keine polynomialen
Algorithmen existieren. Anschaulich gesprochen geht es um einen Handlungsreisenden, der eine Rundreise durch n Städte absolvieren will, wobei er eine möglichst günstige Reiseroute
auswählen will.
Formal betrachtet man eine positive Gewichtsfunktion w (die man beispielsweise als Entfernung
oder Reisezeit interpretieren kann) auf den Kanten des vollständigen Graphen Kn auf n Punkten
und sucht eine Tour (also einen Hamiltonschen Kreis) mit möglichst geringem Gesamtgewicht. Da
das TSP schwer ist, aber eine Vielzahl von praktischen Anwendungen hat, ist man auch an
approximativen Lösungen interessiert. Leider ist selbst die Aufgabe, eine Näherungslösung zu finden, die höchstens das k-fache Gewicht einer optimalen Tour hat, schwer: Die Existenz eines
polynomialen k-approximativen Algorithmus würde bereits die Gleichheit der Komplexitätsklassen
P und NP und damit insbesondere die polynomiale Lösbarkeit des TSP selbst nach sich ziehen.
Diese Situation ändert sich, wenn man sich auf den praktisch besonders relevanten Spezialfall des metrischen TSP einschränkt, bei dem w die Dreiecksungleichung erfüllt. Hier hat Christofides
bereits 1976 ein polynomiales 3
2-approximatives Verfahren angegeben. Trotz intensiver
Bemühungen konnte dieser Approximationsfaktor bis heute nicht verbessert werden. Allerdings
gelang dies, wenn man sich noch mehr spezialisiert, nämlich entweder auf das Euklidische TSP
oder aber auf das TSP mit Gewichten aus 1,2{ }. Im ebenen Euklidischen Fall (also Punkte in der
Euklidischen Ebene mit dem üblichen Euklidischen Abstand) konnte Arora 1996 sogar ein
polynomiales Approximationsschema angeben, also einen parametrisierten Algorithmus, der für gegebenes e > 0 eine 1+e -approximative Lösung mit polynomialer Komplexität bestimmt, nämlich
O n1/e( ). Dieses Resultat hat Herr Sticker in seiner Bachelorarbeit in Einzelheiten ausgearbeitet und
anhand eines Beispiels erläutert.
Mitbetreuung von interdisziplinären Masterarbeiten (ausgegeben von Kollegen außerhalb des Instituts):
Failer Armin: Lösungsverfahren für das Vehicle Routing Problem mit mehreren Depots
Erstgutachter: Prof. Jaehn (WiWi), Zweitgutachter: Prof. Hachenberger
Die kostengünstigste Belieferung von Gütern an Kunden gehört sicher zu den grundlegendsten
Aufgaben eines jeden Logistikunternehmens. Eine daraus resultierende mathematische
Problemstellung, das sog. Vehicle Routing Problem wurde erstmals Ende der 1950-er Jahre von
Pionieren des Operations Research systematisch untersucht. In seiner Masterarbeit beschäftigt
sich Herr Failer mit einer Variation dieser Aufgabe, dem sog. Multiple Depot Vehicle Routing
Problem with Fixed Distribution of Vehicles (kurz: MDVRPFD):
Gegeben sind eine (endliche) Menge von Kundenstandorten und eine (endliche) Menge
von Depots; jedes Depot verfügt über eine Flotte von (endlich) vielen Fahrzeugen. Ziel ist
es, den Bedarf eines jeden Kunden des durch die Depots vertriebenen Produktes (z.B.
Heizöl) zu decken. Dazu bedarf es einerseits einer Zuordnung, welche besagt, welcher
Kunde von welchem Depot aus versorgt wird; des weiteren ist festzulegen, welches Fahr-
zeug eines jeden Depots welchen Kunden bedient. Ferner soll dann jedes Fahrzeug seine
Kunden in einer Rundreise derart abarbeiten, dass die gesamten Versorgungskosten (etwa
die Summe aller Fahrtstrecken) minimiert wird. Dabei ist eine durch die Fahrzeuge
gegebene Kapazitätsobergrenze (Transportvolumen) einzuhalten.
Insgesamt handelt es sich um eine facettenreiche Aufgabe, die sich aus verschiedenartigen ver-
schränkten Teilproblemen zusammensetzt: Dem Auffinden einer optimalen Zuordnung
(assignment), der Gewährleistung von Bedarfen durch den Gütertransport (min cost flow), sowie
die Planung von optimalen Rundreisen (routing). Da bereits das klassische Traveling Salesman
Problem NP-hart ist, ist es nicht verwunderlich, dass kein effizienter Algorithmus für das MDVRPFD
bekannt ist; wahrscheinlich existiert kein solcher Algorithmus. Von daher muss man sich in der
Praxis damit begnügen, Heuristiken zur schnellen Bestimmung einer (hoffentlich guten) Näherung
der unbekannten Optimallösung zu finden. Die Analyse und das Austesten solcher Verfahren für
das MDVRPFD bilden die zentrale Aufgabenstellung der Masterarbeit von Herrn Failer. Dabei
kommt das Programm-Paket Matlab zum Einsatz.
Maahs Miriam: Ablaufplanung am Beispiel der Fußball-Bundesliga
Erstgutachter: Prof. Jaehn (WiWi), Zweitgutachter: Prof. Hachenberger
Die Planung von Turnieren (auch Spielplanerstellung für Sportligen bzw. die Planung eines Double
Round Robin Tournaments) gehört sicher zu den klassischen Anwendungen der kombinatorischen
Optimierung. Beschränkten sich die frühen Arbeiten von de Werra (aus den 1980-er Jahren) noch
weitestgehend auf eine graphentheoretische Formulierung mit dem Ziel der Breackminimierung
(möglichst wenige aufeinanderfolgende Heim- bzw. Auswärtsspiele), so ist die moderne
Ligaplanung viel komplexer geworden: Das enorme Interesse an Sportwettbewerben, allen voran
Fußball-Ligen, erfordert zusätzliche Überlegungen zur Steigerung der sportlichen Attraktivität, der
Wahrung von wirtschaftlichen Interessen von Vereinen und Verbänden sowie von Medien und
Fans. So gehen heutzutage verschiedenartige Methoden aus der Diskreten Mathematik und der
Optimierung, wie die Verwendung von gemischt-ganzzahligen Programmen, diversen
Lösungsstrategien mit Hilfe von Zerlegungstechniken, und moderne Programmierumgebungen in
die Erstellung von Spielplänen ein.
Frau Maahs liefert in ihrer Masterarbeit am Beispiel der Fußball-Bundesliga einen Einblick in dieses
interessante Optimierungsgebiet. Die konkrete Spielplanerstellung erstreckt sich dabei über drei
Phasen: Festlegung der Spielpaarungen der Hinrunde inklusive der Spieltage an denen sie
stattfinden; Festlegung des Heimrechts bei allen Spielpaarungen der Hinrunde; Festlegung der
Anstoßzeiten für jeden Spieltag. Die gesamte Ausarbeitung von Frau Maahs erstreckt sich von der
Beschaffung des konkreten Datenmaterials über die Erstellung der Modelle und die
Implementierung der Verfahren (unter Verwendung des Programm-Pakets CPLEX) hin zu aus-
sagekräftigen Tests.
Netzsch Sebastian: Tourenplanungsprobleme im E-Fulfillment unter Verwendung des Set-
Covering Ansatzes
Erstgutachter: Prof. Klein (WiWi), Zweitgutachter: Prof. Hachenberger
Das sog. Vehicle Routing Problem (VRP) besteht im Wesentlichen aus der Aufgabe, eine möglichst
kostengünstige Versorgung von Kunden an Gütern zu gewährleisten. Dabei verfügt das
versorgende Unternehmen über ein Depot, aus dem die Kunden durch ein oder mehrere Fahr-
zeuge beliefert werden; der Bedarf eines jeden Kunden ist zu decken; kein Fahrzeug darf sein
Transportvolumen überschreiten. Das Auffinden einer Lösung des Problems umfasst insbesondere
die Zerlegung der Menge aller Kunden in einzelne Gruppen, die jeweils vom Depot aus auf einer
Rundreise beliefert werden.
In seiner Masterarbeit befasst sich Herr Netzsch mit einer Variation dieses Themas, dem sog.
Vehicle Routing Problem with Time Windows (VRPTW): Entweder geben die Kunden jeweils eine
Zeitspanne an, in der sie beliefert werden wollen, was zu einer stärkeren Einschränkung auf Seiten
des Lieferanten führt, oder das Unternehmen gibt im Rahmen seiner Routenplanung dem Kunden
Zeitfenster vor. Die in der Arbeit verfolgte generelle Lösungsmethode sieht zunächst vor,
heuristisch eine bestimmte Vielfalt von möglichen Versorgungsrouten zu bestimmen (Bildung eines
Routenpools), um in einer zweiten Phase daraus mit Methoden aus der linearen ganzzahligen
Optimierung eine bestmögliche Überdeckung aller Kunden zu finden. Bei der Implementierung der
Verfahren verwendet Herr Netzsch die Programm-Pakete Matlab und CPLEX ILOG.
Schiegg Thomas: Das Routing Open Shop Problem
Erstgutachter: Prof. Jaehn (WiWi), Zweitgutachter: Prof. Hachenberger
Beim Routing Open Shop Problem handelt es sich um eine kombinatorische Optimierungsaufgabe,
die eine Mischung des bekannten metrischen Traveling Salesman Problems mit dem Open Shop
Problem darstellt. Bei letzterem geht es grob gesprochen darum, eine gewisse Menge von aus
einzelnen Operationen bestehenden Arbeitsvorgängen (Jobs) derart auf dafür verfügbare
Maschinen bearbeiten zu lassen, dass die Gesamtbearbeitungsdauer minimiert wird. Ein Routing
Open Shop Problem tritt beispielsweise auf, wenn man (mehrere) Handlungsreisende mit
Maschinen und die Arbeitsvorgänge mit Städten (oder umgekehrt) assoziiert, an denen die ein-
zelnen Maschinen unterschiedliche Operationen ausführen müssen, um den gesamten Arbeitsplan
zu erfüllen. Als konkretes Beispiel nennt Herr Schiegg in seiner Einleitung die optimale Zeitplanung
eines mobilen Pflegeservice.
Komplexitätstheoretisch betrachtet handelt es beim Routing Open Shop Problem um eine
schwierige Problemstellung, für die es aller Wahrscheinlichkeit nach keinen (deterministischen)
effizienten Algorithmus gibt, der optimale Lösungen produziert. Deshalb behilft man sich in der
Praxis mit approximativen Algorithmen; das sind effiziente (deterministische) Verfahren, die zu
jeder Probleminstanz einen Lösungsvorschlag unterbreiten, der zumindest mit einer bestimmten
Gütegarantie an die unbekannte Optimallösung heranreicht.
Herr Schiegg betrachtet in seiner Masterarbeit ein erst kürzlich von Kononov (2014) vorgestelltes
approximatives Verfahren zur Lösung des Routing Open Shop Problem (kurz: ROS-Algorithmus).
Die Arbeit umfasst eine theoretische Ausarbeitung zum ROS-Algorithmus, dessen Implementie-
rung in der Matlab-Umgebung, sowie umfangreiche Tests an ausgewählten Probleminstanzen
(eine Kombination bestehender Benchmarkprobleme für Open Shop Probleme und für metrische
TSP-Instanzen). Herr Schiegg deckt bei seiner Analyse zahlreiche Ungenauigkeiten der Original-
arbeit auf und bereinigt diese. Des weiteren unterbreitet Herr Schiegg eigene Strategien zur
Vermeidung unnötiger Wartezeiten sowie zur Nachbarschaftssuche, die sich erheblich auf die
Verbesserung der Güte der Resultate auswirken.
5. Vorträge / Reisen
Dieter Jungnickel
Reisen:
Rom, 05.-15.05.2015, Kooperation mit Prof. Ghinelli
Vorträge:
Gießen, 14.11.2015, „Konfigurationen in Endlichen Projektiven Geometrien“, Vortrag am
Baerkolloquium zum Gedenken an Prof. Pickert
Augsburg, 26.11.2015, „Von magischen Quadraten zum Sudoku“, Vortrag in der Reihe
Faszination Mathematik und Physik
Tobias Harks
Reisen:
Amsterdam, 09.-12.12.2015, 11th Conference on Web and Internet Economics
(zusammen mit Anja Huber und Manuel Surek)
Bonn, 13.-18.12.2015, Game Theory Workshop, Hausdorff Institut Bonn
Vorträge:
Amsterdam, 9.12.2015, „Matroids and Polymatroids in Congestion Games“,
Invited Tutorial “Conference on Internet and Network Economics WINE”
Bonn, 13.12.2015, „Uniqueness of Equilibria in Polymatroid Congestion Games“
Trimester in “Combinatorial Optimization”, Hausdoff Center Bonn
6. Veröffentlichungen
Dieter Jungnickel
a) Monographien und Lehrbücher:
Optimierungsmethoden, Springer Spektrum, Heidelberg, 3. Auflage (2015)
b) referierte Zeitschriftenartikel /Proceedings-Artikel
Blocking sets of the classical unital (zusammen mit A. Blokhuis, V. Krčadinac, S.
Rottex, L. Storme, T. Szőnyi, P. Vandendriessche), Finite Fields Appl. 35 (2015), 1-
15
Maximal arcs and quasi-symmetric designs, (zusammen mit V.D. Tonchev),
Designs, Codes and Cryptography, 77 (2015), 365-374
On a theorem of Rigby, J. Geom., DOI 10.1007/s00022-015-0298-7
The characterization problem for designs with the parameters of AG d(n,q)
(zusammen mit K. Metsch), Combinatorica, DOI: 10.1007//s00493-014-3212-2
Tobias Harks
a) Monographien und Lehrbücher:
Neighborhood Technologies: Media and Mathematics of Dynamic Networks,
(with S. Vehlken (Eds.)), Diaphanes (2015)
Special Issue: Algorithmic Game Theory, (with D. Fotakis (Eds.)), Springer, Theory
of Computing Systems (October 2015)
b) referierte Zeitschriftenartikel /Proceedings-Artikel
Equilibria in a Class of Aggregative Location Games, (with M. Klimm), Journal of
Mathematical Economics 61(1), 211-220 (2015)
Congestion Games Viewed from M-convexity, (with S. Fujishige, M.X. Goemans, B.
Peis and R. Zenklusen), Operations Research Letters 43, 329-333 (2015)
Computing Network Tolls with Support Contraints, (with M. Klimm, I. Kleinert and
R.H. Möhring), Networks 65(3), 262-285 (2015)
Bottleneck Routing with Elastic Demands, (with M. Klimm and M. Schneider), In
Proceedings of the 11th Conference on Internet and Network Economics (WINE 2015)
Dirk Hachenberger a) referierte Zeitschriftenartikel /Proceedings-Artikel
Primitive normal bases für quartic and cubic extensions: a geometric approach,
Designs, Codes and Cryptography, 77 (2015), 335-350
Asymptotic existence results for primitive completely normal elements in
extensions of Galois fields, Designs, Codes and Cryptography (2015), DOI
10.1007/s10623-015-0119-x
8. Gäste am Lehrstuhl
Prof. Dr. Berhard Schmidt,
Nanyang Technological University, Singapur (01.08.2014-31.03.2015)
9. Forschungsförderungsmittel, Drittmittel
10. Herausgabe von Zeitschriften
Dieter Jungnickel
Editor-in-Chief, Designs, Codes and Cryptography
Associate Editor, Applicable Algebra in Engineering, Communication and Computing
Associate Editor, Finite Fields and their Applications
Associate Editor, Journal of Combinatorial Mathematics and Combinatorial Computation
Tobias Harks
Associate Editor of OMEGA – The International Journal of Management Science
11. Organisation von Tagungen
Tobias Harks
Organisation des Dagstuhl Seminars “Dynamic Traffic Models in Transportation Science”
(32-0115), 5.-9. Oktober 2015 (mit J. Correa, K. Nagel, B. Peis and M. Skutella)
Organisation des Streams “Game Theory” der International Conference on Operations
Research OR 2015, Vienna, Austria (mit J. Hofbauer and K. Schmedders)
PC member of the 11th Conference on Internet and Network Economics (WINE), 2015,
Amsterdam
