Forschungsinstitut für Diskrete Mathematik
Programmierpraktikum Diskrete Optimierung (P2C1)
Sommersemester 2008
Thema: Multicommodity Flows in Global Routing
In diesem Praktikum soll ein primal-dualer Approximationsalgorithmus implementiert werden,
der in der Verdrahtung höchstintegrierter Logikchips erfolgreich eingesetzt wird.
Das zu lösende Problem besteht darin, eine sehr große Zahl
von elektrischen Verbindungen -
bis zu mehreren Millionen - auf begrenztem Platz so zu realisieren,
dass eine gegebene Zielfunktion, beispielsweise
Gesamtverdrahtungslänge oder Stromverbrauch, optimiert wird.
Die Teilnehmer des Praktikums sollen ein Programm erstellen, das
1) in einem bestimmten Format vorliegende Daten einliest, die eine Instanz des zu
lösenden Verdrahtungsproblems beschreiben,
2) mittels des im Praktikum vorgestellten primal-dualen Approximationsalgorithmus
eine annähernd optimale fraktionale Lösung des Problems berechnet,
3) aus der fraktionalen Lösung mittels Rundung eine ganzzahlige Lösung erzeugt,
4) und zuletzt die durch die Rundung möglicherweise entstandenen Verletzungen
einzelner Nebenbedingungen behebt.
Jeder Teilnehmer soll sein Programm auf einer Reihe frei verfügbarer industrieller
Global-Routing-Benchmarks testen und auswerten.
Die Programmiersprache ist C++.
Vorbesprechung:
Dienstag, den 5. Februar 2008 um 11 Uhr c.t.
im Seminarraum des Forschungsinstitutes für Diskrete Mathematik, Lennéstraße 2
Ansprechpartner:
Dirk Müller,
mueller (at) or.uni-bonn.de,
Tel. 0228 / 73 87 86
Prof.
Dr. B. Korte,
Prof. Dr.
J. Vygen,
Prof. Dr.
S. Hougardy,
Jun.Prof. Dr.
T. Nieberg,
Dr.
U. Brenner