In dieser Arbeit beschäftigen wir uns mit dem quadratischen Zuordnungsproblem (Quadratic Assignment Problem QAP). Das QAP ist ein Problem der kombinatorischen Optimierung und zählt dort mittlerweile zu den klassischen Problemstellungen. Eine der typischen Problemstellungen, die mit Hilfe des QAPs modelliert werden können, sind plänare Zuordnungsprobleme. Bei dieser Klasse von Problemen betrachtet man z.B. ein gegebenes Streckennetz der Bahn mit verschiedenen Verkehrsknoten, an denen sich verschiedene Streckenabschnitte kreuzen. An diesen Verkehrsknoten sollen verschiedene Fabriken errichtet werden, die untereinander in Geschäftsverbindung stehen und sich deswegen gegenseitig mit verschiedenen über das Streckennetz beliefern. In einer Planungsphase zur Anordnung der Fabriken auf jeweils verschiedenen Verkehrsknoten ist bereits bekannt, wie viele Güter von einer Fabrik zu einer anderen transportiert werden. Außerdem ist bekannt, wie lang die Strecken zwischen jeweils zwei Knoten des Streckennetzes sind. An jedem Verkehrsknoten soll genau eine Fabrik errichtet werden. Das Ziel der Planung soll die Minimierung der gesamten zurückzulegenden Strecke der Güter sein. Das heißt, daß insgesamt möglichst viele Güter zwischen den verschiedenen Fabriken auf möglichst kurzen Wegen des Streckennetzes transportiert werden sollen.
Das quadratische Zuordnungsproblem wurde erstmals 1957 in ähnlicher Weise von Koopmans und Beckmann formuliert, um plänare Zuordnungsprobleme der beschriebenen Art zu losen. In dieser ersten Formulierung ging es um die Zuordnung einer Menge von Wirtschaftsresourcen auf eine Menge von Standorten. Hierbei sind dann die Anzahl der Aktivitäten zwischen den Ressourcen und die Entfernungen der Standorte gegeben. Die Kosten der Wirtschaftsaktivitäten steigen proportional mit der Entfernung zweier beteiligter Wirtschaftsresourcen. Ziel ist hier die Minimierung der Kosten, die insgesamt durch die verschiedenen Aktivitaten aufgrund der Entfernung der verschiedenen Ressourcen entstehen.
Inhaltsverzeichnis
- Problemstellungen
- Einführung
- Bezeichnungen
- Das Modell
- Bekannte Probleme in der Formulierung als QAP
- Lösungsmethoden
- Eine einfache untere Schranke
- Gilmour-Lawler-Bound (GLB)
- Vergleich aller zulässigen Lösungen
- Ein Branch & Bound-Algorithmus
- Vorüberlegungen
- Obere und untere Schranken
- Die Störungsmethode
- Das Verzweigungsschrittverfahren.
- Der Algorithmus für Koopmans-Beckmann-Probleme
- Regel alternativer Kosten
- Verkürzung des Suchbaumes.
- Beispiel zur Störungsmethode
- Ein Paralleler Branch & Bound-Algorithmus.
- Die Idee der Parallelisierung.
- Rechenergebnisse
- Linearisierungen
- Linearisierung nach Frieze und Yadegar
- Linearisierung nach Kaufman und Broeckx
- Polyedrische Kombinatorik
- Lokale Optima und Heuristiken
- QAPs mit speziell strukturierten Matrizen
- Matrixstrukturen und deren Erkennung
- Polynomial lösbare Spezialfälle
- 0-1-Probleme
- 0-1-QAP: Beispiele
- Packungen von Graphen
- Graphisomorphismen.
- Graph partitioning
- Server-Problem
- Spezielle 0-1-Probleme
- Minimierung von Rangierkosten.
- Gilmour-Lawler-Bound für 0-1-Probleme
- 0-1-QAP: Beispiele
- Auswertungen und Rechenergebnisse
- Numerischer Vergleich verschiedener B&B-Algorithmen
- Die Branch & Bound-Implementierungen
- Generierung der Testprobleme
- Test der verschiedenen B&B-Implementierungen
- Heuristische Lösungen von QAPS
- Die Heuristik-Implementierungen
- Test der Heuristiken
- Gilmour-Lawler-Bound
- Linearisierungen
- C-Programme zur LP-Erzeugung
- Test der beiden Linearisierungen
- Test des GRID-Algorithmus'
- Schnellere Berechnung der GLB im 0-1-Fall
- Numerischer Vergleich verschiedener B&B-Algorithmen
- Zusammenfassung und Ausblick
Zielsetzung und Themenschwerpunkte
Die vorliegende Diplomarbeit befasst sich mit dem quadratischen Zuordnungsproblem (QAP), einem klassischen Problem der kombinatorischen Optimierung. Ziel dieser Arbeit ist es, verschiedene Lösungsansätze und exakte Methoden für das QAP zu untersuchen und zu vergleichen. Dabei liegt der Fokus auf 0-1-Problemstellungen und deren Lösungsverhalten.
- Formulierung und Modellierung des QAP
- Exakte Lösungsmethoden wie Branch & Bound-Algorithmen
- Heuristiken und Approximationsalgorithmen
- Spezielle 0-1-Problemstellungen und deren Anwendungen
- Numerische Auswertung und Vergleich verschiedener Lösungsansätze
Zusammenfassung der Kapitel
- Kapitel 1: Problemstellungen: Dieses Kapitel führt in die allgemeine Problemstellung des quadratischen Zuordnungsproblems ein. Es werden verschiedene Anwendungsmöglichkeiten des QAPs, insbesondere in der Planungs- und Logistikbranche, beleuchtet. Außerdem werden 0-1-Problemstellungen als wichtige Untergruppe des QAPs vorgestellt und erste Beispiele für die Modellierung von Problemen aus der Graphentheorie mittels QAPs gegeben.
- Kapitel 2: Lösungsmethoden: Dieses Kapitel behandelt verschiedene Lösungsmethoden für das QAP. Neben einer einfachen unteren Schranke und dem Gilmour-Lawler-Bound wird ein Branch & Bound-Algorithmus vorgestellt. Der Algorithmus wird detailliert beschrieben und anhand eines Beispiels illustriert. Außerdem werden parallele Lösungsansätze und Linearisierungsmethoden für das QAP erörtert.
- Kapitel 3: QAPs mit speziell strukturierten Matrizen: In diesem Kapitel werden QAPs mit speziell strukturierten Matrizen untersucht. Es werden verschiedene Matrixstrukturen vorgestellt und deren Erkennung sowie die Möglichkeit, polynomiale Lösungsansätze zu finden, diskutiert.
- Kapitel 4: 0-1-Probleme: Dieses Kapitel beschäftigt sich mit 0-1-Problemstellungen im Kontext des QAPs. Es werden verschiedene Beispiele für 0-1-QAPs aus der Graphentheorie vorgestellt, wie Packungen von Graphen, Graphisomorphismen und Graph Partitionierung. Außerdem wird das Problem der Minimierung von Rangierkosten als weiteres Beispiel für 0-1-QAPs behandelt.
- Kapitel 5: Auswertungen und Rechenergebnisse: In diesem Kapitel werden verschiedene Lösungsansätze für das QAP numerisch verglichen. Dazu werden Branch & Bound-Algorithmen, Heuristiken und Linearisierungsmethoden implementiert und an verschiedenen Testproblemen evaluiert. Die Ergebnisse werden diskutiert und die Leistungsfähigkeit der verschiedenen Ansätze miteinander verglichen.
Schlüsselwörter
Quadratisches Zuordnungsproblem (QAP), kombinatorische Optimierung, 0-1-Probleme, Graphentheorie, Branch & Bound, Heuristiken, Linearisierung, numerische Auswertung, Vergleich, Algorithmen.
- Quote paper
- Markus Lemke (Author), 1998, 0-1 QAP: Lösungsansätze und exakte Methoden, Munich, GRIN Verlag, https://www.grin.com/document/44885
