Plazieren von Zellen: Theorie und Lösung eines quadratischen 0/1- Optimierungsproblems.
Please always quote using this URN: urn:nbn:de:0297-zib-4883
- Die vorliegende Arbeit beschäftigt sich mit dem Plazierungsproblem, welches beim Entwurf elektronischer Schaltungen auftritt. Das Plazierungsproblem modellieren wir als ein quadratisches 0/1 Optimierungsproblem unter linearen Nebenbedingungen und untersuchen das Modell komplexitätstheoretisch. Der zweite Aspekt der Arbeit bezieht sich auf die Lösung praktischer Problembeispiele im sogenannten Sea of cells"-Entwurfsstil. Zur Lösung dieser Beispiele wurde ein Prototyp implementiert und mit state of the art"-Plazierungsverfahren verglichen. Schlie\ss lich werden wir uns mit dem Clusteringproblem, das eine Variante des Mehrfachschnitt-Problems darstellt, beschäftigen. Dabei steht einerseits im Vordergrund, wie diese Probleme heuristisch gelöst werden können und wie die Integration des Ansatzes in das Plazierungsprogramm erfolgt. Andererseits soll das Clusteringproblem polyedrisch untersucht werden.
| Author: | Robert Weismantel |
|---|---|
| Document Type: | Doctoral Thesis |
| Date of first Publication: | 1992/07/17 |
| Series (Serial Number): | ZIB-Report (TR-92-03) |
| ZIB-Reportnumber: | TR-92-03 |
