Stellen Sie sich vor, Sie planen im nächsten Urlaub, Ihre Lieblingsstädte in Europa zu besuchen. Dabei möchten Sie jede Stadt genau einmal besuchen und anschließend nach Wien zurückkehren. Da Ihr Budget nicht sehr groß ist, suchen Sie nach der kostengünstigsten Rundreise. Schon bei 16 Städten ist die Anzahl aller möglichen Routen aber bereits größer als 650 Milliarden. Die optimale Tour zu berechnen, würde gut 20 Jahre in Anspruch nehmen. Bis dahin müsste die Reise freilich warten.
Allerdings nicht, wenn man auf moderne Mathematik und Informatik zurückgreift. MathematikerInnen können mit Operations-Research-Methoden relativ rasch Näherungslösungen für die bestmögliche Tour finden. Das nützen NetzwerkplanerInnen. Denn diese stehen beim Design von Glasfasernetzwerken, Kommunikationsnetzwerken oder Gas- und Wärmeversorgungssystemen vor ähnlichen Problemen wie bei der Planung der Urlaubsrundreise beschrieben.
Last Mile
"Typischerweise wird immer die kostengünstigste Verbindung zwischen den Kunden und dem Hauptverteilerknoten gesucht, die den Bedarf aller Kunden erfüllt und zusätzliche Netzwerkeinschränkungen - wie begrenzte Kapazitäten oder Ausfallssicherheit - berücksichtigt", erklärt Mag. Dr. Ivana Ljubic vom Institut für Statistik und Decision Support Systems. Sei arbeitet seit 1. Jänner 2007 im Rahmen des Hertha-Firnberg-Programms "Algorithmische Lösungen für Last-Mile-Netzwerke" aus. Der Begriff 'last mile' bezeichnet den letzten Abschnitt der Leitung, die bei Strom- und Gasversorgungs- sowie bei Telekommunikationsnetzen zum Endverbraucher führt.
Mathematische Kochrezepte
"Im Projekt will ich Algorithmen entwickeln, die mathematische Modelle und Methoden in der Praxis einsetzen, um 'Real World'-Probleme lösen zu können", hält Ivana Ljubic fest. Algorithmen versteht sie wie Kochrezepte: Sie beschreiben bestimmte Schritte, die zu einer Lösung führen, so die Forscherin. Seit dem Zweiten Weltkrieg werden so genannte Operations-Research-Methoden erfolgreich in der Praxis - vor allem für Logistik und Planung - eingesetzt.
Aber chello
Vieles ist dabei aber noch ungelöst. Im Gegensatz zu Köchen steht die Mathematik vor großen Herausforderungen, wenn es darum geht zu beweisen, dass ihre "Rezepte" richtig sind. Ivana Ljubic' Forschungsprojekt hat seinen Schwerpunkt im Design von Glasfasernetzwerken. Dabei soll einer Menge Kunden eine schnelle Breitbandverbindung gewährleistet werden. Die Gesamtgrabungskosten, die beim Verlegen der Leitungen in den Straßen entstehen, sollen so minimal wie möglich bleiben. In diesem simplifizierten Beispiel müssen die PlanerInnen den besten Straßen- und Kreuzungsverlauf des Kabels aussuchen.
Keine halben Sachen
"Probleme wie jenes der Kabelverlegung sind seit 200 Jahren als das 'Steinerbaum-Problem' bekannt, ein kombinatorisches Optimierungsproblem", erklärt Ivana Ljubic. Eine erschwerende Komponente ist, dass manche Variablen nur ganze Zahlen sein dürfen, dem man mit Mixed-Integer-Programming-Formulierungen beikommen will. Genauso wie beim Modellieren der Städte-Rundreise sind nämlich Lösungen, die vorschlagen, man solle zu fünfzig Prozent nach Paris und zu fünfzig Prozent nach London fahren, inakzeptabel. "Zumindest solange Sie keine gespaltene Persönlichkeit sind", lacht die Forscherin.
"Spannendes Feld"
Dass ihre Arbeit nicht aus reiner Theorie besteht, sondern die Algorithmen im täglichen Leben Anwendung finden und so vom allgemeinen Nutzen für die Gesellschaft sind, empfindet die Forscherin bei ihrer Arbeit als sehr zufrieden stellend. Und Ivana Ljubic, die 2004 an der TU Wien dissertierte und dafür bereits ein DOC-Stipendium der Akademie der Wissenschaften erhielt, ist dabei sehr erfolgreich, wie nun auch das Hertha-Firnberg-Stipendium zeigt. (hh)
Die Mathematikerin und Informatikerin Mag. Dr. Ivana Ljubic forscht im Rahmen des Herta-Firnberg-Programms des FWF am Projekt "Algorithmische Lösungen für Last-Mile-Netzwerke". Das Projekt begann am 1. Jänner 2007 und hat eine Laufzeit von drei Jahren.
|
