Forschungsinstitut für Diskrete Mathematik

Programmierpraktikum Diskrete Optimierung (Modul P2C1)

Sommersemester 2015

Thema: Darstellungen von Rechteckpackungen

Rechteck-Packungsprobleme haben viele wichtige Anwendungen, insbesondere beim Entwurf von höchstintegrierten Logikchips. Dabei verfolgt man unterschiedliche Optimierungsziele (z.B. Minimierung des Flächenverbrauchs oder Optimierung von Verbindungslängen zwischen den Rechtecken). Die meisten Packungsprobleme erweisen sich dabei als NP-schwer. Um dennoch optimale Packungen zu berechnen, kann man sich enumerativer Methoden bedienen. Dafür muß man Anordnungen von Rechtecken kompakt kodieren können, und man muß in der Lage sein, aus einer Kodierung auf effiziente Art eine zugehörige Rechteckpackung zu bestimmen. In diesem Praktikum sollen verschiedene Repräsentierungen von Rechteckanordnungen implementiert und zur Berechnung optimaler Packungen verwendet werden.
Hier kann eine genaue Beschreibung der einzelnen Aufgaben heruntergeladen werden, und hier kann eine Liste mit den Teilnehmern und Beteuern heruntergeladen werden.

Termine des Abschlußpräsentationen:

Donnerstag, 9. Juli: Donnerstag, 30. Juli:

Kleine Testinstanzen:

Instanzen mit gegebener Plazierung (für die Eintiegsaufgabe): Die angegebenen Plazierungen sind alle überlappungsfrei (man konstruiert sich leicht Instanzen mit Überlappungen daraus).

Packungsinstanzen:

Bilder von Packungen der Pack-Instanzen 1 bis 9 finden sich hier.

Weitere Instanzen werden folgen.

Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner,
Dr. N. Hähnle