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
1 Problemstellungen
1.1 Einführung
1.2 Bezeichnungen
1.3 Das Modell
1.4 Bekannte Probleme in der Formulierung als QAP
2 Lösungsmethoden
2.1 Eine einfache untere Schranke
2.2 Gilmour-Lawler-Bound (GLB)
2.3 Vergleich aller zulässigen Lösungen
2.4 Ein Branch&Bound-Algorithmus
2.4.1 Vorüberlegungen
2.4.2 Obere und untere Schranken
2.4.3 Die Störungsmethode
2.4.4 Das Verzweigungsschrittverfahren
2.4.5 Der Algorithmus für Koopmans-Beckmann-Probleme
2.4.6 Regel alternativer Kosten
2.4.7 Verkürzung des Suchbaumes
2.4.8 Beispiel zur Störungsmethode
2.5 Ein Paralleler Branch & Bound-Algorithmus
2.5.1 Die Idee der Parallelisierung
2.5.2 Rechenergebnisse
2.6 Linearisierungen
2.6.1 Linearisierung nach Frieze und Yadegar
2.6.2 Linearisierung nach Kaufman und Broeckx
2.7 Polyedrische Kombinatorik
2.8 Lokale Optima und Heuristiken
3 QAPs mit speziell strukturierten Matrizen
3.1 Matrixstrukturen und deren Erkennung
3.2 Polynomial lösbare Spezialfälle
4 0-1-Probleme
4.1 0-1-QAP: Beispiele
4.1.1 Packungen von Graphen
4.1.2 Graphisomorphismen
4.1.3 Graphpartitioning
4.1.4 Server-Problem
4.2 Spezielle 0-1-Probleme
4.3 Gilmour-Lawler-Bound für 0-1-Probleme
4.4 Minimierung von Rangierkosten
4.4.1 Modellierung als QAP
4.4.2 Rechenergebnisse
5 Auswertungen und Rechenergebnisse
5.1 Numerischer Vergleich verschiedener B&B-Algorithmen
5.1.1 Die Branch & Bound-Implementierungen
5.1.2 Generierung der Testprobleme
5.1.3 Test der verschiedenen B&B-Implementierungen
5.2 Heuristische Lösungen von QAPs
5.2.1 Die Heuristik-Implementierungen
5.2.2 Test der Heuristiken
5.3 Gilmour-Lawler-Bound
5.4 Linearisierungen
5.4.1 C-Programme zur LP-Erzeugung
5.4.2 Test der beiden Linearisierungen
5.5 Test des GRID-Algorithmus
5.6 Schnellere Berechnung der GLB im 0-1-Fall
6 Zusammenfassung und Ausblick
Zielsetzung & Themen
Diese Arbeit untersucht das quadratische Zuordnungsproblem (Quadratic Assignment Problem, QAP), ein klassisches Problem der kombinatorischen Optimierung. Das primäre Ziel ist die Analyse und Implementierung exakter Lösungsmethoden (speziell Branch & Bound-Verfahren) sowie heuristischer Ansätze, um die Komplexität dieser NP-schweren Problemstellung zu bewältigen.
- Mathematische Modellierung von QAPs und Anwendung auf praktische Szenarien
- Entwicklung und Implementierung effizienter unterer Schranken (GLB)
- Untersuchung von Branch & Bound-Algorithmen und ihrer Optimierung durch Störungsmethoden
- Analyse von 0-1-Problemen und deren spezielle Lösungsansätze
- Umfangreiche numerische Evaluierung verschiedener Algorithmen und Heuristiken
Auszug aus dem Buch
1.1 Einführung
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 planare 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 Gütern ü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 planare Zuordnungsprobleme der beschriebenen Art zu lösen. 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 Resourcen 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 Aktivitäten aufgrund der Entfernung der verschiedenen Resourcen entstehen.
Zusammenfassung der Kapitel
1 Problemstellungen: Einführung in die Definition und mathematische Formulierung des quadratischen Zuordnungsproblems sowie Darstellung praktischer Anwendungsbeispiele.
2 Lösungsmethoden: Vorstellung exakter Verfahren wie Branch & Bound sowie lokaler Suchmethoden und Heuristiken zur Schrankenbestimmung.
3 QAPs mit speziell strukturierten Matrizen: Analyse von Spezialfällen, bei denen besondere Matrixstrukturen eine polynomiale Lösbarkeit ermöglichen.
4 0-1-Probleme: Betrachtung von Problemen mit 0-1-Matrizen, inklusive spezifischer Anwendungsbeispiele wie Graphenpackungen und Server-Problemen.
5 Auswertungen und Rechenergebnisse: Detaillierte numerische Analyse und Leistungsvergleich der implementierten Algorithmen anhand von Testdaten.
6 Zusammenfassung und Ausblick: Resümee der erzielten Erkenntnisse und Diskussion möglicher zukünftiger Forschungsansätze.
Schlüsselwörter
Quadratisches Zuordnungsproblem, QAP, Kombinatorische Optimierung, Branch & Bound, Gilmour-Lawler-Bound, Linearisierung, 0-1-Matrizen, Heuristik, Simulated Annealing, Graphpartitioning, Komplexitätstheorie, NP-schwer, Schrankenbestimmung, Optimierung, Algorithmen.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit dem quadratischen Zuordnungsproblem (QAP), einem bekannten und rechnerisch sehr anspruchsvollen Problem der kombinatorischen Optimierung, für das verschiedene Lösungsansätze untersucht und implementiert werden.
Welche zentralen Themenfelder werden behandelt?
Die Arbeit deckt die theoretische Modellierung, exakte Lösungsverfahren (insbesondere Branch & Bound), Heuristiken (wie Simulated Annealing) sowie die Untersuchung spezieller Matrixstrukturen und 0-1-Probleme ab.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel ist die systematische Untersuchung, Entwicklung und Implementierung effizienter Algorithmen zur Lösung von QAPs, um die Performance bei der Bestimmung optimaler oder nahezu optimaler Zuordnungen zu verbessern.
Welche wissenschaftliche Methode wird primär verwendet?
Es wird eine Kombination aus mathematischer Modellierung und algorithmischer Implementierung genutzt, ergänzt durch eine umfangreiche numerische Testreihe zur Evaluierung der Laufzeiteffizienz.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die methodische Entwicklung von B&B-Algorithmen und deren Optimierung (z.B. durch Störungsmethoden), die Behandlung spezieller 0-1-Probleme sowie die praktische Leistungsbewertung der Ansätze.
Welche Schlüsselwörter charakterisieren die Arbeit?
QAP, Kombinatorische Optimierung, Branch & Bound, Heuristiken, 0-1-Probleme, Gilmour-Lawler-Bound und Komplexitätsanalyse.
Welche Rolle spielen die 0-1-Probleme in der Arbeit?
Sie stellen einen wichtigen Spezialfall dar, da sich für diese Klasse von Matrizen oft effizientere Lösungswege oder stärkere Vereinfachungen finden lassen, etwa bei der Gilmour-Lawler-Schranke.
Warum ist das QAP für die Forschung so interessant?
Das QAP ist NP-schwer und damit allgemein schwer lösbar, was es zu einem klassischen Testfeld für neue Optimierungs- und Schrankenbestimmungsverfahren macht.
- Quote paper
- Markus Lemke (Author), 1998, 0-1 QAP: Lösungsansätze und exakte Methoden, Munich, GRIN Verlag, https://www.grin.com/document/44885
