Diplomarbeit Institut für Angewandte Mathematik Abteilung Mathematische Optimierung TU Braunschweig

0 - 1 QAP : Lösungsansätze & exakte Methoden

eingereicht von

Markus Lemke

1998

Inhaltsverzeichnis

1. Problemstellungen ... 1
1.1 Einführung ... 1
1.2 Bezeichnungen ... 3
1.3 Das Modell ... 5
1.4 Bekannte Probleme in der Formulierung als QAP ... 7

2. Lösungsmethoden ... 10
2.1 Eine einfache untere Schranke ... 10
2.2 Gilmour-Lawler-Bound ( GLB ) ... 13
2.3 Vergleich aller zulässigen Lösungen ... 15
2.4 Ein Branch & Bound- Algorithmus ... 16
2.4.1 Vorüberlegungen ... 16
2.4.2 Obere und untere Schranken ... 17
2.4.3  Die Störungsmethode ... 21
2.4.4 Das Verzweigungsschrittverfahren ... 23
2.4.5 Der Algorithmus für Koopmans-Beckmann-Probleme ... 26
2.4.6 Regel alternativer Kosten ... 28
2.4.7 Verkürzung des Suchbaumes ... 29
2.4.8 Beispiel zur Störungsmethode ... 30
2.5 Ein Paralleler Branch & Bound-Algorithmus ... 32
2.5.1 Die Idee der Parallelisierung ... 32
2.5.2 Rechenergebnisse ... 33
2.6 Linearisierungen ... 33
2.6.1 Linearisierung nach Frieze und Yadegar ... 34
2.6.2 Linearisierung nach Kaufman und Broeckx ... 36
2.7 Polyedrische Kombinatorik ... 38
2.8 Lokale Optimaund Heuristiken ... 39

3. QAPs mit speziell strukturierten Matrizen ... 44
3.1 Matrixstrukturen und deren Erkennung ... 44
3.2 Polynomial lösbare Spezialfalle ... 51

4. 0-1-Probleme ... 55
4.1 0-1-QAP Beispiele ... 55
4.1.1 Packungen von Graphen ... 55
4.1.2 Graphisomorphismen ... 57
4.1.3 Graphpartitioning ... 58
4.1.4 Server-Problem ... 59
4.2 Spezielle Probleme ... 60
4.3 Gilmour - Lawler - Bound für 0-1- Probleme ... 71
4.4 Minimierung von Rangierkosten ... 72
4.4.1 Modellierung als QAP ... 72
4.4.2 Rechenergebnisse ... 74

5.Auswertungen und Rechenergebnisse ... 77
5.1 Numerischer Vergleich verschiedener B&B Algorithmen ... 77
5.1.1 Die Branch & Bound Implementierungen ... 78
5.1.2 Generierung der Testprobleme ... 81
5.1.3 Test der verschiedenen B & B Implementierungen ... 81
5.2  Heuristische Lösungen von QAPs ... 86
5.2.1 Die Heuristik Implementierungen ... 86
5.2.2 Test der Heuristiken ... 87
5.3 Gilmour-Lawler-Bound ... 89
5.4 Linearisierungen ... 90
5.4.1 C-Programme zur LP-Erzeugung ... 90
5.4.2 Test der beiden Linearisierungen ... 91
5.5 Test des Grid- Algorithmus ... 92
5.6 Schnellere Berechnung der GLB im  0-1- Fall ... 93

6. Zusammenfassung und Ausblick A ... 95

A. Kurzbeschreibung C-Programme ... 97

B. Lösungen zu Problemen aus der QAPLIB ... 101

Problemstellungen

Einführung

In dieser Arbeit beschäftigen wir uns mit dem quadratischen Zuordnungsproblem ( Quadratic Assignment Problem  = ). 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 verschiedenen 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 Steckennetzes 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, dass 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 Wirtschaftsressourcen 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 Wirtschaftsressourcen. Ziel ist hier die Minimierung der Kosten, die insgesamt durch die verschiedenen Aktivitäten aufgrund der Entfernung der verschiedenen Ressourcen entstehen.

Darüber hinaus ist das QAP Forschungsgegenstand in Bereichen des Scheduling, dem VLSI-Design und der statistischen Datenanalyse. Allerdings wollen wir uns in dieser Arbeit darauf beschränken nach Betrachten der allgemeinen Problemstellung hauptsächlich 0-1- Problemstellungen und deren Lösungsverhalten zu untersuchen.

Bei den 0-1-Problemstellungen schränkt man die Wahl der Werte für Verbindungen und Anzahlen auf die Werte 0 und 1 ein. Bei dem Problem der oben beschriebenen Art würde dies bedeuten, daß eine Streckenverbindung nur die Länge 1 oder 0 haben kann und ebenso entweder 1 oder 0 Güter transportiert werden sollen. Eine häufige Anwendung der 0-1-Problerne liegt aufgrund dieser Wertebeschränkung im Bereich der Graphentheorie. Denn die Adjazenzmatrizen von Graphen lassen sich vollständig mit Hilfe der Werte 0 und 1 beschreiben. (Dazu setzt man den Wert in der i-ten Zeile und j-ten Spalte innerhalb der Adjazenzmatrix auf 1, falls es eine Kante vom Knoten i zum Knoten J des Graphen gibt. Falls keine solche Kante existiert. wird dieser Wert auf 0 gesetzt.) Dazu ein kleines Beispiel:

Es soll nachgeprüft werden, ob eine Packung eines Graphen G2 in einen Graphen GI existiert. Eine solche Packung existiert genau dann. wenn eine Abbildung der Knoten des Graphen G2 in die Knotenmenge des Graphen G_l existiert. so dass alle Kanten des Graphen G2 auf kanten des Graphen GI abgebildet werden. Zur Modellierung als quadratisches Zuordnungsproblem benötigen wir in diesem Beispiel die .Adjazenzmatrix des Graphen G₂ und die Adjazenzmatrix des Komplementgraphen zu GI. Existiert eine Packung des Graphen in den Graphen GI. so überschneiden sich bei dieser Packung keine Kanten aus dem Graphen und dem Komplementgraphen zu G_l. Auf die entsprechende Formulierung als quadratisches Zuordnungsproblem gehen wir im Abschnitt 3.1.1 ein. Dort werden wir noch weitere Beispiele aus den1 Bereich der 0-1-Probleme kennen lernen (Graphpartitionierung. Graphisomorphismen).

Im Gegensatz zum linearen Zuordnungsproblem. das einen Spezialfall der quadratischen Zuordnung darstellt. gibt es bislang keine Möglichkeit, das allgemeine quadratische Zuordnungsproblem in polynomialer Zeit zu lösen. Sahni und Gonzalez zeigten 1976 in ^[22], dass die allgemeine Problemstellung des QAP NP-hart ist. Sie zeigen in ihrer .Arbeit, dass das .Auffinden einer Lösung des QAPs in polynomialer Zeit bedeutete, dass die Frage nach der Existenz eines Hamiltonischen Kreises innerhalb eines Graphen in polynomialer Zeit entschieden werden könnte. Dieses Problem, ob ein solcher Kreis in einem Graphen existiert, ist als NP-vollständig bekannt. Darüber hinaus wird gezeigt, dass selbst das Problem der Bestimmung einer 5-optinialen Lösung NP-vollständig ist. Das heißt, dass sich das Problem in der Komplexität nicht vereinfacht, wenn es um das Auffinden einer Lösung geht. die sich von der optimalen um maximal  ε unterscheidet.

[...]

[22] C. Roucairol, A parallel branch and bound algorithm for the quadratic assignment problem, Discrete Applied Mathematics 18, 1987, 221-225