Forschungsinstitut für Diskrete Mathematik

Programmierpraktikum Diskrete Optimierung (Modul P2C1)

Sommersemester 2018

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 muss man Anordnungen von Rechtecken kompakt kodieren können, und man muss 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.

Termine des Abschlusspräsentationen:

Freitag, 20. Juli: Dienstag, 24. Juli:

Hier kann eine genaue Beschreibung der einzelnen Aufgaben heruntergeladen werden, und hier kann eine Liste mit den Teilnehmern und Betreuern heruntergeladen werden.

Kleine Testinstanzen:

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

Packungsinstanzen:

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

Allgemeine Hinweise zum Programmieren.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner