LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Praktikum Diskrete Optimierung (SS 1999):

Optimierung der Struktur von Rechnernetzen

(Ein Rechnernetz)

Dozent: Prof. Dr. Angelika Steger
Zeit: 2 Stunden Vorlesung
4+X Stunden Bearbeiten der Probleme (6 SWS)
Raum: Vorlesung bzw. Praktikumsbesprechung im Raum S2229
Bereich: Informatik I (alte Prüfungsordnung)
Informatik III (neue Prüfungsordnung)
(Details hier)
Voraussetzungen: Grundkenntnisse über Entwurf und Implementierung von Algorithmen, Motivation und Kreativität
Praktikumsleiter: Alexander Hall, Thomas Schickinger
Anmeldung: zentrale Einschreibung in der HP-Halle
Scheinerwerb: Schein für aktive Mitarbeit an der Erarbeitung der Lösungen

Praktikumstermin: Di 14:00 (s.t.) - 15:30, Raum S2229

Beginn: 11.05.99
[Hintergrund] [Inhalt] [Ziele] [Thema im SS'99] [Durchführung] [Literatur]

Informationen für Teilnehmer


Hintergrund

Unter Diskreter Optimierung versteht man die Suche nach einer optimalen Lösung zu einem Problem mit diskretem Suchraum. Solche Probleme treten in der Praxis an vielen Stellen auf. Als Beispiele seien genannt:
* Einplanung von Aufträgen bei Fertigungsstraßen
* Zuteilung von Bandbreite in Kommunikationsnetzen
* Berechnung des Chiplayouts bei VLSI
Die bei der Diskreten Optimierung betrachteten Probleme lassen sich gewöhnlich dadurch charakterisieren, daß der Suchraum endlich ist und somit eine optimale Lösung durch vollständige Suche gefunden werden könnte. Da der Suchraum jedoch meistens zwar endlich aber riesig ist (und die exakte Lösung der Probleme nicht selten NP-schwer ist), muß man in der Praxis auf andere Methoden ausweichen. Hierbei gibt es folgende Ansätze:
* Geschickte Organisation der Suche (z.B. Branch-and-Bound),
* Heuristische Verfahren, unterteilbar in
  • Problemspezifische Heuristiken
  • Allgemeine Techniken (z. B. Genetische Algorithmen, Simulated Annealing, Tabu Search),
* Approximationsverfahren, die eine Lösung mit garantierter Qualität berechnen.
Eine ‹bersicht über die verschiedenen Ansätze gibt ein Tutorial von Ronald L. Radin, Purdue University, Indiana.

Inhalt

Im Rahmen des Praktikums sollen Student(inn)en verschiedene Techniken zur Lösung diskreter Optimierungsprobleme kennenlernen und diese an einem konkreten Problem umsetzen.

Bei der Auswahl der Probleme werden solche Probleme bevorzugt, die einen Bezug zur Praxis haben. Ferner sollen die im Praktikum erarbeiteten Lösungen mit Referenzimplementierungen bzw. Benchmarks verglichen werden, sofern solche Daten zum behandelten Problem verfügbar sind. Ein wünschenswertes Fernziel besteht darin, die Leistung solcher Referenzimplementierungen zu erreichen oder sogar zu überbieten.

Grundsätzlich gliedert sich das Praktikum in zwei Teile:
* Einarbeitungsphase: Grundlegende Techniken werden erklärt und einfache Implementierungen davon umgesetzt.
* Problemlösungsphase: Jeder Bearbeiter bzw. jedes Team überlegt sich einen Ansatz, wobei selbstverständlich eine oder mehrere der zuvor behandelten Techniken zum Einsatz kommen können, und versucht davon eine möglichst leistungsstarke Implementierung vorzunehmen. Hierzu ist ist nötig, den eigenen Ansatz sauber umzusetzen und so weit wie möglich zu optimieren.
In einer speziellen zweistündigen Praktikumsvorlesung werden die bei der Diskreten Optimierung verwendeten Verfahren erläutert. Hierbei geht es mehr um das Verständnis der Verfahren als um den theoretischen Hintergrund. Oftmals sind die Verfahren auch rein heuristischer Natur, so daß kaum theoretische Aussagen getroffen werden können. Vorausgesetzt werden neben guten Programmierkenntnissen Grundkenntnisse über Design und Implementierung von Algorithmen, wie sie beispielsweise in der Vorlesungen "Effiziente Algorithmen und Datenstrukturen" vermittelt werden. Der Besuch dieser Vorlesungen ist empfehlenswert, aber nicht unbedingt erforderlich.


Ziele

Mit dem Praktikum werden mehrere Ziele verfolgt:
* Tieferes Verständnis der Methoden zur Diskreten Optimierung,
* Erfahrungen bei der Entwicklung hochoptimierter Software für rechenintensive Probleme.
* Spaß an der Herausforderung, die bestmögliche Leistung aus dem verfügbaren Rechensystem "herauszukitzeln".

Thema im SS'99

Im Sommersemester 1999 beschäftigen wir uns mit der Optimierung der Struktur von Rechnernetzen. Im Zusammenhang mit der Neustrukturierung des B-WiN (Deutsches Breitband-Wissenschaftsnetz) des DFN-Vereins ist dieses Problem von aktueller Bedeutung.

Es geht dabei um folgende Fragestellung:

Wie kann ein Rechnernetz strukturiert werden, um ein gegebenes Verkehrsaufkommen mit minimalen Leitungskosten zu bewältigen?

Im Detail sieht dies wie folgt aus: Es wird vorgegeben, welche Bandbreite zwischen zwei Knoten im Netz benötigt wird. Das berechnete Netz muß in der Lage sein, diese Bandbreiten zur Verfügung zu stellen. Dazu werden Leitungen angemietet, für die je nach Länge und Bandbreite Kosten anfallen. Das Optimierungsziel besteht darin, diese Kosten zu minimieren.

Dieses Problem wird an der TU München vom Lehrstuhl Prof. Jessen untersucht. Volker Fischer, der an diesem Projekt arbeitet, versorgt uns dankenswerterweise mit Hintergrundinformationen und wird im Rahmen des Praktikum eine kurze Einführung in die zugrundeliegende Problematik geben.


Durchführung

Grundsätzlich soll das Praktikum nicht strikt dem klassischen Schema Aufgabe-Lösung-Korrektur folgen. Besonders im zweiten Teil erhalten die Teilnehmer(innen) viel Freiheit bei der Umsetzung ihres Lösungsansatzes. Es geht eben nicht darum, bekannte Algorithmen zu implementieren, sondern es sind Kreativität und Ideen gefragt. Aus diesem Grund erwarten wir von Interessenten, daß sie ein hohes Maß an Motivation und Selbständigkeit mitbringen. Es gibt keine Musterlösung und keinen garantiert erfolgreichen Ansatz, an dem man sich orientieren kann, sondern die Teilnehmer(innen) sollen eigene Lösungsmöglichkeiten erkunden, wobei sie selbstverständlich von den Praktikumsbetreuern bestmöglich unterstützt werden.

Pro Woche findet eine Praktikumssitzung statt, bei der neue Techniken eingeführt, die zu lösenden Aufgaben vorgestellt und die bisherigen Ergebnisse und/oder Schwierigkeiten besprochen werden. Bei akuten Problemen können die Betreuer selbstverständlich auch außerhalb dieser Sitzung angesprochen werden.

Die Lösungen werden gewöhnlich in C++ unter Verwendung geeigneter Bibliotheken implementiert. Der Phantasie der Teilnehmer(innen) sind allerdings auch hier a priori keine Grenze gesetzt. Wenn Sie ein gutes Argument finden, warum eine andere oder zusätzliche Bibliothek vorteilhaft wäre, so ist es durchaus möglich, daß sich Ihr Vorschlag durchsetzt. Wir wollen Probleme statt vorgefertigter Aufgaben lösen.

Die Bearbeitung der Praktikumsaufgaben kann entweder auf unseren Lehrstuhl-Rechern (S 2237), in der Sunhalle oder auch auf einem Linux-Rechner zu Hause erfolgen (sofern die nötigen Bibliotheken für Linux verfügbar sind, was jedoch im Normalfall kein Problem darstellen sollte).

Um den Praktikums-Schein zu erhalten, müssen einfache Lösungen für alle vorgestellten Ansätze erstellt werden und darüberhinaus eine erkennbare Anstrengung bei der Erstellung einer optimierten Lösung unternommen werden. Wir bieten eine interessante und herausfordernde Aufgabe und erwarten im Gegenzug überdurchschnittliches Engagement. Auf dieser Grundlage werden auch die Praktikums-Scheine vergeben werden.

WICHTIG: Das Praktikum Diskrete Optimierung zählt nach der alten Prüfungsordnung als Wahlpflichtpraktikum im Bereich Informatik I (Praktische Informatik), nach der neuen Prüfungsordnung (gültig ab November 1996) aber im Bereich Informatik III (Theoretische Informatik). Student(inn)en, die nach der neuen Prüfungsordnung DHP machen müssen, können den Schein nicht als Praktikumsschein zu Informatik I verwenden. Student(inn)en, die zwischen alter und neuer Prüfungsordnung wählen dürfen, können den Schein wahlweise als Schein zu Informatik I oder zu Informatik III verwenden. Für Details hier clicken!


Literatur

* Die Darstellung der verschiedenen heuristischen Optimierungsverfahren orientiert sich an folgendem Buch:
C. R. Reeves (Hrsg.), Modern Heuristic Techniques For Combinatorial Problems, Blackwell Scientific Publications, 1993.
* Der "Vater" der genetischen Algorithmen:
D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.

Thomas Schickinger
Last modified: Fri Jun 18 11:15:28 METDST 1999