Verleihung der Diplom- und Masterarbeitspreise 1998

von ANDREAS DREXL, KIEL

Auch in diesem Jahr hatte die GOR zu einem studentischen Wettbewerb aufgerufen, bei dem in 1997 abgeschlossene Diplomarbeiten auf dem Gebiet des Operations Research ausgezeichnet werden sollten.

Insgesamt wurden sechs Arbeiten eingereicht. Die Arbeiten deckten ein breites Spektrum an Modellen, Methoden und Anwendungen des Operations Research ab. Alle waren von den Betreuern als hervorragend eingestuft worden. Die Jury hatte damit die Aufgabe herauszufinden, welche dieser Diplomarbeiten als preiswürdig einzuschätzen seien.
Als Mitglieder der Jury fungierten:Prof. Dr. Andreas Drexl (Vorsitz), Christian–Albrechts–Universität zu Kiel, Herbert Fürstenwerth, 3M – Deutschland GmbH und Prof. Dr. Erwin Pesch, Universität Bonn.

Nach gründlicher Lektüre der eingereichten Arbeiten kam die Jury zu dem Ergebnis, daß nicht nur eine, sondern drei Arbeiten gleichermaßen preiswürdig seien. Im einzelnen handelt es sich dabei um die folgenden Arbeiten:

Andreas Bley (Betreuer: Prof. Dr. M. Grötschel)
"Node–Disjoint Length–Restricted Paths"

Die Diplomarbeit befaßt sich mit graphentheoretischen Problemen, die in der Telekommunikation bei der Planung von Netzwerken von besonderer Bedeutung sind. Hauptgegenstand der Untersuchung sind Fragestellungen des Knotenzusammenhangs von Graphen, deren Beantwortung wichtige Voraussetzung für den kostengünstigen Entwurf von Netzwerken bei gleichzeitiger Sicherung der Übertragungsqualität ist. Insbesondere bei Anwendungen mit hoher Datenübertragung (wie zum Beispiel bei Audioübertragungen oder Echtzeit–Videokonferenzen) sind diese Probleme von großer Relevanz.

Die Diplomarbeit enthält einen theoretischen und einen praxisorientierten Teil, der durch Rechenergebnisse anhand praktischer Daten abgerundet wird. Der theoretische Teil der Diplomarbeit analysiert die Komplexität von »Single–Demand« Problemen, deren Gegenstand die Bestimmung disjunkter Pfade mit beschränkter Länge zwischen zwei Knoten eines Graphen ist. Mehrere neue Komplexitätsergebnisse werden bewiesen, für einige bereits bekannte Komplexitätsaussagen werden elegantere Beweise vorgestellt. Wichtige theoretische Aussagen über die Güte polynomialer Approximationsalgorithmen werden hergeleitet.

Der praxisorientierte Teil der Diplomarbeit befaßt sich mit algorithmischen Aspekten zur Lösung der untersuchten Probleme. Die gesamte Breite algorithmischer Ansätze wird dabei erfaßt, angefangen bei Preprocessing–Techniken zur Problemreduktion, über Heuristiken, die auf max–flow und min–cost–flow Techniken zurückgreifen, bis hin zu Branch–and–Bound–Verfahren. Trotz des Schwierigkeitsgrades der betrachteten Probleme sind die experimentellen Ergebnisse, die anhand praktischer Daten aus der Mobilfunkindustrie gewonnen wurden, von guter bis sehr guter Qualität.

Thomas Nitschke (Betreuer: Priv.–Doz. Dr. J. Köhler)
"Dynamic Fleet Assignment – Modell eines Optimierungsproblems der Flugplanung und Lösung durch ein exaktes Verfahren"

Die Arbeit beschäftigt sich mit einer Optimierungsaufgabe, die im Rahmen der mittelfristigen Planung von Fluggesellschaften auftritt: Das sogenannte Dynamic Fleet Assignment ordnet vorgebenen Flugstrecken unter gewissen Nebenbedingungen Flugzeugtypen und genaue Flugzeiten zu.

Die Interpretation als Mehrgüternetzwerkflußproblem macht die Fragestellung neben der praktischen Relevanz theoretisch interessant. Bereits mehrfach waren Untersuchungen zu Fleet Assignment–Problemen sowohl aus komplexitätstheoretischer Sicht als auch aus dem Blickwinkel von Lösungsverfahren Gegenstand der Literatur. Der Ansatz von Herrn Nitschke unterscheidet sich von vorherigen Darstellungen durch die gleichzeitige Betrachtung der beiden Teilaufgaben einer optimierten Zuordnung von Flugzeiten einerseits und der Zuordnung von Flugzeugtypen – dem klassischen Fleet Assignment – andererseits. Insbesondere aus den praktischen Erfordernissen heraus verfolgt die Arbeit drei wesentliche Ziele: (1) Eine detaillierte Darstellung der Entwicklung eines mathematischen Entscheidungsmodells. Die Analyse des Flugplanungsproblems aus Sicht der technischen Rahmenbedingungen und aus betriebswirtschaftlicher Sicht führt hierbei auf ein ganzzahliges Mehrgüternetzwerkflußproblem. (2) Eine Literaturauswertung zur Evaluierung verschiedener Verfahren. Im Rahmen der Darstellung der relevanten Ergebnisse und Algorithmen werden insbesondere klassische LP–Methoden und die Lagrange-Technik behandelt. (3) Die Entwicklung eines exakten Lösungsverfahrens. Es wird eine auf dem Prinzip der Spaltengenerierung basierende Methode entwickelt, die in ein Branch–and–Bound–Verfahren eingebettet ist. Besonderes Augenmerk wird dabei auf die praktische Implementierung des Verfahrens unter Nutzung moderner Optimierungswerkzeuge gelegt. Die experimentelle Auswertung erfolgt im wesentlichen anhand der Daten echter Planungsprobleme.

Mit der Arbeit werden Einsichten in die Struktur des Planungsproblems, des entstehenden kombinatorischen Optimierungsproblems und in die Eigenschaften der rechentechnischen Lösung gewonnen und einer praktischen Verwendbarkeit zugeführt.

Martin Oellrich (Betreuer: Prof. Dr. R. Möhring)
"Algorithms for the Construction of Reliable Network Platforms in Telecommunication Networks"

Diese Diplomarbeit entstand im Rahmen eines Projektes mit der Telekom. Sie befaßt sich mit der Planung von »Netzwerkplattformen«, die Subnetzwerke in größeren Telekommunikationsnetzwerken repräsentieren. Ein typischer Anwendungsfall sieht wie folgt aus: Ausgangspunkt ist ein Kontrakt zwischen der Telekom und z.B. einer Bank. Er regelt die Überlassung einer Reihe von Verbindungen, von denen jede ein Paar von Niederlassungs–Standorten verbindet. Aufgabe der Telekom als Eigner des physikalischen Netzwerkes ist es, die von der Firma nachgefragten Verbindungen bereitzustellen. Das Ergebnis wird als Einbettung bezeichnet.

Schwierig wird das Problem deshalb, weil Zuverlässigkeitsforderungen erfüllt werden müssen. Zuverlässigkeit bedeutet in diesem Kontext, daß alle Verbindungen physikalisch voneinander unabhängig sein müssen, die Einbettungen sind dann disjunkt. Zuverlässigkeit kostet jedoch Geld, folglich sind kostenminimale Einbettungen von Interesse.

Bisher gab es keine algorithmische Lösung für dieses Problem. Netzwerkplaner waren auf ihre Erfahrung angewiesen, heuristische Lösungen das Ergebnis. Im Rahmen der Diplomarbeit modelliert Herr Oellrich das Problem mathematisch. Ferner entwickelt er effiziente exakte Verfahren (u.a. vom Typ Dynamische Optimierung, Branch–and–Bound) zur Lösung des Problems.
Eine experimentelle Untersuchung zeigt, daß das Laufzeitverhalten der Verfahren sehr gut ist. Von der Telekom wurden die Ideen wegen ihres Kostensenkungspotentials sehr positiv aufgenommen.

Die Laudatio wurde von Herrn Pesch vorgetragen, da Herr Drexl verhindert war.