Fachprojekt Algorithm Engineering (Wintersemester 2012/2013)

Algorithm Engineering beinhaltet das Design von Algorithmen, ihre theoretische Analyse, die Implementierung, sowie die experimentelle Evaluation am Rechner. Dabei liegt der Schwerpunkt auf anwendungsrelevanten Problemen.

In diesem Fachprojekt liegt der Fokus auf dem klassischen Steinerbaumproblem (STP, Steiner tree problem):

Für einen gegebenen Graphen mit Kantenkosten und einer Menge an speziellen Knoten , den sogenannten Terminalen, wird ein Teilgraph von gesucht, der alle Terminale miteinander verbindet und minimale Kosten hat.

Das STP ist ein NP-vollständiges, kombinatorisches Optimierungsproblem, welches gut durch mathematische Programmierung (z.B. Branch & Cut) exakt gelöst werden kann. Für die Praxis ist es wichtig, die gegebenen Instanzen durch Preprocessing zu bearbeiten, um die Graphgröße zu reduzieren. Für das STP gibt es einige Preprocessing-Methoden, die einen Graphen extrem verkleinern können und die Lösbarkeit enorm verbessern.

In diesem Fachprojekt sollen unterschiedliche Preprocessing-Methoden für das Steinerbaumproblem implementiert werden. Anschließend sollen diese experimentell untersucht und deren Performanz verglichen werden.

Die Studierenden arbeiten dabei in Teams mit Gruppengröße . Es wird einen regelmäßigen Termin in der Woche für alle geben, bei dem Zwischenergebnisse, Aufgaben oder Probleme besprochen werden. Der Termin wird dienstags, 14-18 Uhr sein.

Die Implementierung wird in C++ erfolgen und verwendet das OGDF (Open Graph Drawing Framework).

Die Anmeldung ist bis zum 05.06. verfügbar und können Sie hier finden.

Das regelmäßige Treffen findet jeden Dienstag, 14.00-18.00 Uhr statt; im Besprechungsraum 202 oder im Rechnerpool 204 (jeweils OH14).

Das erste Treffen ist am 09.10. um 14:15 Uhr im Raum 202, OH 14. Die folgenden Termine stehen noch nicht fest.

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Prof. Petra Mutzel oder Bernd Zey.