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

INHALTSVERZEICHNIS

  i  

  Inhaltsverzeichnis  

1  Problemstellungen  1

1.1  Einf uhrung  1

1.2  Bezeichnungen  3

1.3  Das Modell  5

1.4  Bekannte Probleme in der Formulierung als QAP  7

2  L osungsmethoden  10

2.1  Eine einfache untere Schranke  10

2.2  Gilmour-Lawler Bound (GLB)  13

2.3  Vergleich aller zul assigen L osungen  15

2.4  Ein Branch Bound-Algorithmus  16

2.4.1  Vor uberlegungen  16

2.4.2  Obere und untere Schranken  17

2.4.3  Die St orungsmethode  21

2.4.4  Das Verzweigungsschrittverfahren  23

2.4.5  Der Algorithmus f ur Koopmans-Beckmann Probleme  26

2.4.6  Regel alternativer Kosten  28

2.4.7  Verk urzung des Suchbaumes  29

2.4.8  Beispiel zur St orungsmethode  30

2.5  Ein Paralleler Branch Bound-Algorithmu s  32

2.5.1  Die Idee der Parallelisierung  32

2.5.2  Rechenergebnisse  33

2.6  Linearisierungen  33

2.6.1  Linearisierung nach F rieze und Yadegar  34

2.6.2  Linearisierung nach Kaufman und Broeckx  36

2.7  Polyedrische Kombinatorik  38

2.8  Lokale Optima und Heuristike n  39

3  QAPs mit speziell strukturierten Matrizen  44

3.1  Matrixstrukturen und deren Erkennung  44

3.2  Polynomial l osbare Spezialf alle  51

INHALTSVERZEICHNIS

  ii  

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 0 1 Probleme  60

4.3  Gilmour-Lawler Bound f ur 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 v erschiedener 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 osungen von QAPs  86

5.2.1  Die Heuristik-Implementierungen  86

5.2.2  Test der Heuristike n  87

5.3  Gilmour-Law l e r B o u n d  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-Algorithmu s '  92

5.6  Schnellere Berechnung der GLB im 0 1 Fall  93

6  Zusammenfassung und Ausblick  95

  A Kurzbeschreibung C-Programme  97

  B L osungen zu Problemen aus der QAPLIB  101

1

1 Problemstellungen

1.1 Einf uhrung

In dieser Arbeit besch aftigen wir uns mit dem quadratischen Zuordnungsproblem (Quadratic Assignment Problem Q A P ). Das QAP ist ein Problem der kombinatorischen Optimierung und z ahlt dort mittlerweile zu den klassischen Problemstellungen. Eine der typischen Problemstellungen, die mit Hilfe des QAPs modelliert werden k onnen, sind planare Zuordnungsprobleme. Bei dieser Klasse von Problemen betrachtet man z.B. ein gegebenes Streckennetz der Bahn mit verschiedenen Verkehrsknoten, an denen sich v erschiedene Streckenabschnitte kreuzen. An diesen Vehrkehrsknoten sollen verschiedene Fabriken errichtet werden, die un-tereinander in Gesch aftsverbindung stehen und sich deswegen gegenseitig mit verschiedenen G utern uber das Streckennetz beliefern. In einer Planungsphase zur Anordnung der Fabriken auf jeweils verschiedenen Verkehrsknoten ist bereits bekannt, wie viele G uter von einer Fabrik zu einer anderen transportiert werden. Auuerdem 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 uckzulegenden Strecke der G uter sein. Das heiit, daa insgesamt m oglichst viele G uter zwischen den verschie-

denen Fabriken auf m oglichst kurzen Wegen des Streckennetzes transportiert werden sollen. Das quadratische Zuordnungsproblem wurde erstmals 1957 in ahnlicher Weise von Koopmans und Beckmann formuliert, um planare Zuordnungsprobleme der beschriebenen Art zu l osen. 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 aten zwischen den Resourcen und die Entfernungen der Standorte gegeben. Die Kosten der Wirtschafts- aktivit aten steigen proportional mit der Entfernung zweier beteiligter Wirtschaftsresourcen.

KAPITEL 1. PROBLEMSTELLUNGEN 2

aufgrund der Entfernung der verschiedenen Resourcen entstehen.

Dar uber 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 anken nach Betrachten der allgemeinen Problemstellung haupts achlich 0-1-Problemstellungen und deren L osungsverhalten zu untersuchen.

Bei den 0-1-Problemstellungen schr ankt man die Wahl der Werte f ur Verbindungen und Anzahlen auf die Werte 0 und 1 ein. Bei dem Problem der oben beschriebenen Art w urde dies bedeuten, daa eine Streckenverbindung nur die L ange 1 oder 0 haben kann und ebenso entweder 1 oder 0 G uter transportiert werden sollen. Eine h auuge Anwendung der 0-1-Probleme liegt aufgrund dieser Wertebeschr ankung im Bereich der Graphentheorie. Denn die Adjazenzmatrizen von Graphen lassen sich v ollst andig 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 uft werden, ob eine Packung eines Graphen G 2 in einen Graphen G 1 existiert. Eine solche Packung existiert genau dann, wenn eine Abbildung der Knoten des Graphen G ² in die Knotenmenge des Graphen G 1 existiert, so daa alle Kanten des Graphen G 2 auf Kanten des Graphen G 1 abgebildet werden. Zur Modellierung als quadratisches Zuordnungsproblem ben otigen wir in diesem Beispiel die Adjazenzmatrix des Graphen G 2 und die Adjazenzmatrix des Komplementgraphen zu G 1 . Existiert eine Packung des Graphen G 2 in den Graphen uberschneiden sich bei dieser Packung keine Kanten aus dem Graphen G 2 und dem G 1 , s o

Komplementgraphen zu G 1 . Auf die entsprechende Formulierung als quadratisches Zuordnungsproblem gehen wir im Abschnitt 4.1.1 ein. Dort werden wir noch w eitere Beispiele aus dem Bereich der 0-1-Probleme kennenlernen (Graphpartitionierung, Graphisomorphismen).

Im Gegensatz zum linearen Zuordnungsproblem, das einen Spezialfall der quadratischen Zu-ordnung darstellt, gibt es bislang keine M oglichkeit, das allgemeine quadratische Zuordnungsproblem in polynomialer Zeit zu l osen. Sahni und Gonzalez zeigten 1976 in 22], daa die allgemeine Problemstellung des QAP NP-hart ist. Sie zeigen in ihrer Arbeit, daa das Auunden einer L osung des QAPs in polynomialer Zeit bedeutete, daa die Frage nach der Existenz eines Hamiltonischen Kreises innerhalb eines Graphen in polynomialer Zeit entschieden werden k onnte. Dieses Problem, ob ein solcher Kreis in einem Graphen existiert, ist als N P vollst andig bekannt. Dar uber hinaus wird gezeigt, daa selbst das Problem der Bestimmung einer "-optimalen L osung N P -vollst andig ist. Das heiit, daa sich das Problem in der Komplexit at nicht v ereinfacht, wenn es um das Auunden einer L osung geht, die sich v on der optimalen um maximal " unterscheidet.

Das QAP ist eines der am schwierigsten zu l osenden Optimierungsprobleme. Es ist z.B. allgemein nicht m oglich, global optimale L osungen f ur Probleme mit mehr als 20 Knoten (z. B.

1.2. BEZEICHNUNGEN 3

Verkehrsknoten wie im ersten Beispiel) zu bestimmen. Zu den erfolgreichsten Methoden bei der exakten L osung von QAPs geh oren Branch & Bound-Algorithmen, von denen wir einen speziellen im Abschnitt 2.4 kennenlernen werden. Allerdings ist der dort behandelte Ansatz noch nicht der erfolgreichste. In einem Artikel von Roucairol 20] wird ein paralleler Branch & Bound-Algorithmus f ur die L osung quadratischer Zuordnungsprobleme vorgestellt. Mit Hilfe eines Parallelrechners wurden dort Zuordnungsprobleme mit Daten bis zu einer Gr ooe von 25 Knoten exakt gel ost.

Allerdings gibt es einige Spezialf alle, die mit polynomiellem Aufwand l osbar sind. Um solche F alle zu betrachten, besch aftigen wir uns im Kapitel 3 mit speziellen Matrixstrukturen und deren Einnuu auf das L osungsverhalten. Ebenso werden im Abschnitt 2.8 einige Heuristiken vorgestellt, die im Fall hoher Dimensionen des QAPs bereits recht gute Ergebnisse erzielen.

Viele bekannte kombinatorische Optimierungsprobleme lassen sich z w ar als QAP formulieren, werden mit diesem Ansatz aber in der Regel nicht g e l ost, wie z.B. das Travelling Salesman Problem und einige Probleme aus der Graphentheorie. Bevor wir verschiedene Formulierungen von Problemen als QAP vorstellen, ben otigen wir einige hilfreiche Deenitionen.

1.2 Bezeichnungen

Ein QAP habe die Dimension oder die Gr ooe n, w enn in dem Problem genau n Zuordnungen getrooen werden sollen. Das bedeutet, daa das Beispiel der Fabrikzuordnung die Dimension oder Gr ooe n hat, wenn genau n Fabriken genau n verschiedenen Verkehrsknoten zugeordnet werden sollen. Mit n soll durchgehend die Problemgr ooe bezeichnet werden.

Die m oglichen L osungen eines gegebenen QAPs der Dimension n, w erden durch P ermutationen der L ange n beschrieben. D. h. daa jeder Permutation 2 S n ein Zielfunktionswert der Minimierungs- bzw. Optimierungsaufgabe zugeordnet werden kann. Die Gruppe aller Permutationen der L ange n ist die symmetrische Gruppe der Ordnung n und soll im weiteren mit S n bezeichnet werden. F ur die Elemente dieser Gruppe gilt: Eine Permutation der L ange n ist ein Automorphismus der Menge f1 : : : n g auf sich selbst, der jedem Element zwischen 1 und n wieder ein solches Element zuordnet. F ur eine solche Abbildung schreibt man in Tableauschreibweise

1 2 3 : : : n !

=

(1) (2) (3) : : :(n)

oder kurz = ( (1) (2) : : : (n)) mit f1 : : : n g = f(1) : : : (n)g. Dabei bezeichne (i) gerade den Wert, auf den i durch abgebildet wird. F ur eine L osung des QAPs bedeutet dies, daa z. B. durch eine Permutation einer Fabrik i ein Verkehrsknoten (i) zugeordnet wird. { Wir werden h auug 0 als Bezeichnung einer optimalen L osung schreiben.

KAPITEL 1. PROBLEMSTELLUNGEN 4

Mit der Identit at id bezeichnen wir die Permutation id = ( 1 : : : n ), die keinen Elementtausch vornimmt.

Die Eingabedaten quadratischer Zuordnungsprobleme werden durch quadratische Matrizen, d.h. Matrizen mit gleicher Anzahl an Reihen und Spalten, mit Eintr agen aus dem Bereich d e r positiven reellen Zahlen (I R ⁺ ) beschrieben. (Im 0-1-Fall gerade nur aus der Menge f0 1g). Die Klasse der positiven reellen Matrizen mit n Zeilen und n Spalten wird in der gesamten Arbeit mit I R ⁿⁿ bezeichnet (der Index ⁺ wird nicht mitgef uhrt). Die Dimension der Eingabematrizen stimmt mit der Dimension eines QAPs uberein. In dem Beispiel der Fabrikzuordnung mit n

Fabriken bestehen die Eingabedaten gerade aus zwei nn-Matrizen. In der einen nn-Matrix A werden die Mengen der G uter gespeichert, die pro Tag zwischen jeweils zwei Fabriken i und j transportiert werden sollen. In einer weiteren n n-Matrix B werden die Entfernungen von einem Verkehrsknoten k zu einem anderen Knoten l gespeichert. Zus atzlich mag es in einigen F allen sinnvoll sein, in einer weiteren Matrix C Kosten zu ber ucksichtigen, die bei einer bestimmten Zuordnung einer Fabrik i auf einen Knotenpunkt k anfallen. Diese Matrizen wollen wir einheitlich m i t A = ( a ij ) ii j =1:::: n 2 I R ⁿⁿ , B = ( b kl ) kkl =1:::: n 2 I R ⁿⁿ und C = ( c ik ) iik =1::::n 2 I R ⁿⁿ bezeichnen. Abk urzend schreiben wir A = ( a ij ), B = ( b kl ) bzw. C = ( c ik ). Z. T. werden die Eintr age der Matrizen zur besseren Lesbarkeit statt a i j auch m i t a ii j bezeichnet.

Analog zu der Bezeichnung der Eintr age einer Matrix mit zwei Indizes (z.B. a ij ) bezeichnen wir die Eintr age eines Vektors x 2 I R ⁿ mit einem Index (x 2 I R ⁿ = ( x 1 x 2 :::: x n )).

Um sp ater auftauchende Algorithmen bez uglich ihrer Laufzeitkomplexit at vergleichen zu k onnen, folgen wir den Bezeichnungen aus 8]. In unserem Fall der Betrachtung von QAPs bezeichnen wir mit n gerade die Dimension oder die Gr ooe eines gegebenen Problems. Die Laufzeit eines Algorithmus' soll anhand der Anzahl an elementaren Rechenoperationen angegeben werden k onnen. Findet man zu einem Algorithmus ein Polynom p(n), das von der Eingabegr ooe n abh angt und das die Anzahl an maximal ben otigten elementaren Rechenoperationen des Algorithmus' von oben ann ahert, so sagt man, daa ein Algorithmus eine L osung in O(p(n)) ndet.

Wir unterscheiden 3 verschiedene Komplexit atsklassen. Seien g und f zwei Funktionen mit g : I N ! I N n 7 ! g(n) und f : I N ! I N n 7 ! f(n), dann ist

(g(n)) = f f(n) j 9 c 1 c 2 0 : c 1 g(n) f(n) c 2 g(n) g 1.

O(g(n)) = f f(n) j 9 c > 0 : f(n) < c g (n) g 2.

(g(n)) = f f(n) j 9 c > 0 : c g (n) f(n) g : 3.

Bezeichnet man mit f z. B. die Zeitkomplexit at eines Algorithmus' , und ist z. B.

1.3. DAS MODELL 5

f(n) 2 O(n ² ), so sagt man auch, der Algorithmus ist in O(n ² ). Das bedeutet, daa jedes Problem, das mit dem Algorithmus gel ost werden kann, in weniger als c n ² elementaren Rechenoperationen gel ost wird (mit einer f ur einen festen Algorithmus bestimmbaren Konstante c 2 I R).

Durch Einf uhrung dieser drei Komplexit atsklassen lassen sich unabh angig von der Gr ooe uber die Laufzeit einiger Problemklassen machen. Die und Struktur eines Problems Aussagen

allgemeinen Probleme, die in dieser Arbeit zun achst betrachtet werden, lassen sich durch keinen Algorithmus l osen, dessen Laufzeitkomplexit at durch e i n P olynom beschr ankt werden kann. Allerdings werden wir in Kapitel 3 und Kapitel 4 einige Spezialf alle kennenlernen, die sich in polynomialer Zeit l osen lassen. Das bedeutet, daa in diesen F allen ein Polynom in n gefunden werden kann, das die Anzahl an elementaren Rechenoperationen zur L osung eines Problems beschr ankt.

1.3 Das Modell

Legt man der Modellierung des QAPs die anfangs betrachtete Zuordnung von Fabriken zu-grunde, so erreicht man das Ziel der Minimierung, indem die g unstigste Zuordnung von Fabriken i auf Knoten k ermittelt wird, mit ii k 2 f 1 : : : n g. Zur Modellierung ben otigt man die Vorgabe der Anzahl an Fabriken (= Anzahl der Knoten) n, die Matrix A = ( a ij ) 2 I R ⁿⁿ der zu erwartenden t aglichen Transporteinheiten von einer Fabrik i zur Fabrik j und die Matrix B = ( b kl ) 2 I R ⁿⁿ der Entfernungen der Knoten k zu Knoten l. Z u s atzlich mag das Errichten einer Fabrik i auf einem Knoten k die Kosten c ik verursachen, die ebenfalls zu einer Matrix C = ( c ik ) 2 I R ⁿⁿ zusammengefaat werden. Damit l aat sich die Minimierungsaufgabe mathematisch durch

X X X n n n

a ij b (i)(j) + c i i (i) min (1.1)

2Sn i=1 j=1 i=1

formulieren. Die Zielfunktion des Problems zu gegebenen Matrizen AA B C und gegebener Permutation 2 S n l aat sich a b k urzend Z(AA B C ) s c hreiben. H auug werden Probleme ohne die Kostenmatrix C der Form

X X n n

a ij b (i) (j) min (1.2)

2Sn i=1 j=1

mit Zielfunktion Z(AA B ) betrachtet. Eine Optimall osung 0 des Problems w urde in unserem Beispiel durch die optimale Zuordnung

Fabrik i 7 ! Knoten 0 (i) i = 1 : : : n

repr asentiert.

KAPITEL 1. PROBLEMSTELLUNGEN 6

Beispiel 1.1 Betrachten wir z.B. die Zuordnung von 4 Fabriken auf 4 Knoten eines Eisenbahnnetzes, zwischen denen t aglich paarweise mehrere Hundert Produkte transportiert werden sollen. Gegeben sind die Entfernungen der Knoten voneinander und die Anzahl der Produkte, die t aglich zwischen jeweils zwei Fabriken transportiert werden sollen.

Anzahl Produkte (Matrix A) p r o T ag Entfernungen (Matrix B) i n k m / / von # nach ! 1 2 3 4 von # nach ! 1 2 3 4

Eine Optimall osung ist durch 0 = ( 2 1 4 3 ) mit Zielfunktionswert z 0 = 30 114 gegeben, das bedeutet, daa t aglich mindestens 30 114 km von allen Produkten insgesamt zur uckgelegt werden.

Koopmans-Beckmann-Probleme

Seinen Ursprung hat das QAP in der Formulierung von Koopmans und Beckmann im Jahre 1957 als quadratisches kombinatorisches Zuordnungsproblem. Damals wurde damit die Zuweisung einer Menge von Wirtschaftsaktivit aten auf eine Menge von Standorten modelliert. { Aus dieser Formulierung ist auch ersichtlich, woher der Ausdruck " quadratisch\ stammt. Denn das Problem, das unter (1.1) formuliert wird, l aat sich aquivalent in ein Optimierungsproblem mit quadratischer Zielfunktion umformen. Dazu ben otigen wir die folgende

Deenition 1.1 X = ( x ij ) iij=1::::n heiit Permutationsmatrix, wenn die folgenden drei Bedingungen erf ullt sind X n

x ij = 1 j = 1 :::: n (1.3) ⁱ⁼¹ X n

(1.4)

x ij 2 f 0 1g (1.5)

n bezeichne den Raum aller Permutationsmatrizen aus dem I R ⁿⁿ .

1.4. BEKANNTE PROBLEME IN DER FORMULIERUNG ALS QAP 7

Setzt man nun die Variablen x ij folgendermaaen

( 1 falls Resource i dem Standort j zugeordnet wird

(1.6)

so k onnen wir das Problem mit Hilfe des folgenden Satzes umformulieren.

Satz 1.2 Es gibt eine bijektive Zuordnung, die jeder Permutation 2 S n genau eine Permutationsmatrix X 2 n zuordnet.

Beweis. Sei 2 S n gegeben. Setze in einer Matrix X = ( x ij ) 2 I R ⁿⁿ die Eintr age x ij i, j = 1, ...,n wie folgt

( 1 falls (i) = j

x ij :=

0 sonst

dann erf ullt X = ( x ij ) die Eigenschaften der Deenition 1.1, da die Abbildung 2 S ⁿ ein Automorphismus der Menge f1 :::: ng ist. Ist umgekehrt eine Permutationsmatrix

X = ( x ij ) 2 I R ⁿⁿ gegeben, so l aat sich eine Permutation 2 S n eindeutig durch

(i) : = j falls x ij = 1

konstruieren. ( (i) 6 = j falls x ij = 0)

zu (1.1) aquivalente Formulierung des quadratischen Zuordnungsproblems auf dem Raum der 2 Sei X 2 n Permutationsmatrix mit den Eigenschaften der Deenition 1.1, so ergibt sich die

^{n n n n n n X=(x} ij ⁾²ⁿ i=1 j=1 k=1 a ij b kl x ik x jl + i=1

l=1 k=1 Permutationsmatrizen mit gegebenen Matrizen AA B und C. c ik x ik

min

X X X X X X

(1.7)

Hier ergibt sich die Formulierung mit quadratischer Zielfunktion.

1.4 Bekannte Probleme in der Formulierung als QAP

Optimierung einer Schreibmaschinentastatur Burkard und OOermann besch aftigten sich 1977 in 6] mit der Aufgabe, die Buchstaben auf einer Schreibmaschinentastatur f ur verschiedene Sprachen so anzuordnen, daa Texte in der jeweiligen Sprache m oglichst schnell geschrieben werden k onnen. Um dieses Problem einigermaaen zufriedenstellend zu l osen, sind aufwendige Ausz ahlungen von Buchstabenpaaren und die Ermittlung der H auugkeiten der einzelnen Paare durchzuf uhren. Auuerdem ist durch er-

KAPITEL 1. PROBLEMSTELLUNGEN 8

einer Taste j ben otigt wird. Nach Erhebung dieser Daten l aat sich das Problem als quadratisches Zuordnungsproblem formulieren. Beschr ankt man sich wie Burkard und OOermann auf die Buchstaben des Alphabets erhalten wir ein 26-dimensionales Problem.

Sei nun a ij die Zeit, die ben otigt wird, um nach D r

ucken der Taste i die Taste j anzuschlagen

^{26 26} 2Sn i=1

a ij b ^{(i) (j)} L ost man dieses Problem, erh alt man durch die Optimall osung 0 die optimale Anordnung der Tasten auf einer Schreibmaschinentastatur, so daa zum Schreiben eines Textes ein Minimum an Zeit ben otigt wird. Leider ist dieses Problem der Dimension 26 zu groo, um es mit den bislang bekannten Methoden optimal zu l osen ¹ . Darum wurde bei dieser Problembehandlung nur eine lokale Suchmethode eingesetzt. Die lokalen L osungen erbrachten aber schon eine

Verbesserung der Schnelligkeit beim Schreiben von Texten von etwa 1 0 % .

Planung eines Krankenhauslayouts Bei der Planung eines Krankenhauskomplexes ist es sinnvoll, die Kliniken innerhalb des Geb audes so anzuordnen, daa Patienten, die nacheinander mehrere Kliniken zwecks verschiedener Untersuchungen aufsuchen m ussen, m oglichst kurze Distanzen zur ucklegen (siehe 10]).

Allerdings sollte zus atzlich b e r ucksichtigt werden, daa die Wege schwerkranker oder verletzter Patienten zwischen zwei f ur deren Behandlung typischen Kliniken oder Stationen h oher zu gewichten sind. Plant man n Kliniken an ebensovielen Pl atzen innerhalb des Geb audes unterzubringen, so faat man die gewichteten H auugkeiten vom Besuch einer Station j nach einer Station i in einer Matrix A = ( a ij ) 2 I R ⁿⁿ und die Entfernungen von einem Ort k zu einem anderen Ort l in einer Matrix B = ( b kl ) 2 I R ⁿⁿ zusammen. Durch 2 S n sei eine

Zuordnung von Stationen i auf Orte (i) gegeben. Damit kann das Ziel der Wegeminimierung des von den Patienten zur uckzulegenden Gesamtweges durch das L osen der Aufgabe

1.4. BEKANNTE PROBLEME IN DER FORMULIERUNG ALS QAP 9

X X ^{n n} a ij b (i)(j) min

2Sn i=1 j=1

erreicht w erden. Dabei ist a ij b kl der Beitrag zum Gesamtweg, wenn Station i dem Platz k und die Station j dem Platz l zugeordnet wird.

Ein weiteres Beispiel f ur das Location-Problem ndet sich bei der Verteilung der Institute einer Universit at auf einem Campus (siehe 9]) mit gleichem Ziel der Minimierung des Weges, den Studenten und Professoren t aglich zwischen den Instituten und anderen Einrichtungen der Universit at zur ucklegen.

Modulvernetzung

Im technischen Bereich tritt das Problem der Vernetzung n verschiedener Module auf (siehe 21]), bei der m oglichst kurze Leiterverbindungen zwischen vernetzten Modulen i und j existieren sollen. F ur die Umsetzung steht eine Steckplatte mit n Steckpl atzen zur Verf ugung, wobei die Abst ande der Steckpl atze voneinander bekannt sind (h auug in Form eines Gitternetzes). Auuerdem ist der Modulnetzplan bekannt. Diese Informationen lassen sich in Matrizen AA B 2 I R ⁿⁿ erfassen.

( 1 falls Verbindung vom Modul i zum Modul j existieren soll

a ij =

0 sonst

b kl = Abstand von Steckplatz k zum Steckplatz l Um die gesamte Leiterl ange zu minimieren, l ost man das folgende QAP , X X ^{n n} a ij b (i)(j) min

2Sn i=1 j=1

d.h. man versucht eine optimale Anordnung der n Module auf der Steckplatte zu erhalten.

Travelling-Salesman Problem (TSP)

Das TSP l aat sich als quadratisches Zuordnungsproblem formulieren. F ur die eine ben otigte Matrix A 2 I R ⁿⁿ

ubernimmt man die Entfernungsmatrix des TSP. Die zweite Matrix B 2 I R ⁿⁿ ist dann gerade eine Permutationsmatrix mit zyklischer Permutation. Eine opti- n n 2Sn i=1 j=1 male L osung 0 2 S n der Aufgabe min X X

a ij b (i) (j)

dar.

stellt die optimale Rundreise

KAPITEL 2. L OSUNGSMETHODEN 10

2 L osungsmethoden

Dieses Kapitel soll sich mit einigen L osungsmethoden f ur das QAP besch aftigen. Dabei werden wir zwei grundlegende Klassen unterscheiden. Zum einen werden dies exakte Methoden zur optimalen L osung eines QAPs sein und zum anderen Heuristiken, die in der Regel nur lokale L osungsmethoden darstellen. Da wir im Bereich der exakten Methoden im Abschnitt 2.4 einen speziellen Branch&Bound-Algorithmus kennenlernen werden, ist es notwendig, sich zun achst mit dem Auunden von unteren Schranken f ur ein gegebenes Problem zu besch aftigen. (Aufgrund des Ziels der Minimierung der Zielfunktion stellt bereits jede zul assige L osung ur die Optimall osung dar). eine obere Schranke f

2.1 Eine einfache untere Schranke

Im folgenden bezeichnen wir kurz mit LB eine untere Schranke ( Lower Bound) eines QAPs. Beim Konstruieren von Verfahren zum Auunden unterer Schranken eines QAPs gibt es zun achst einmal eine recht sinnvolle und hilfreiche Deenition.

Deenition 2.1 Seien aa b 2 I R ⁿ . Deeniere

n P

< a b > ; := min a i b ⁽ⁱ⁾ P ^{2Sn i=1} < a b > + := max i=1 2Sn

minimales und n

a i b (i) maximales Skalarprodukt. Seien a ⁺ 2 I R ⁿ (und b ^; 2 I R ⁿ ) V ektoren, die entstehen, wenn die Eintr age eines Vektors

a 2 I R ⁿ aufsteigend (und die Eintr age eines Vektors b 2 I R ⁿ absteigend) sortiert werden. Dann gilt

a ⁺ i a ⁺ i+1 i = 1 :::: n ; 1 fa ⁺ i j 1 i ng = fa i j 1 i ng

2.1. EINE EINFACHE UNTERE SCHRANKE 11

Satz 2.2 Das minimale und maximale Skalarprodukt l aat sich in O(n log n) berechnen und es gilt < a b > ; = < a ⁺ b ^; > und

< a b > + = < a ⁺ b ⁺ > .

Beweis. Der Beweis beschr ankt sich auf die erste Gleichung (die zweite ist analog zu zeigen.) Seien aa b 2 I R ⁿ . Ohne Einschr ankung seien die Koordinaten a i mit i = 1 : : : n des Vektors a bereits monoton nicht steigend ¹ . Ist b nicht monoton fallend, so gibt es Koeezienten j und k (j < k ) mit

b j > b k a j a k mit a j b j + a k b k a j b k + a k b j

Vertausche nun j und k durch eine Transposition 2 S n , dann folgt daraus (mit b = ( b (1) b (2) :::: b (n) ) ) X X n n

Der Vektor b l aat sich durch O(n log n) solche Transpositionen absteigend sortieren (siehe 8]

S. 163 .). Faat man alle Transpositionen 2 S n zu einer Permutation 2 S n zusammen, so erh alt man

< a b > < a b > = < a b > ;

2 wobei b = ( b (1) b (2) : : : b (n) ) gerade monoton nicht fallend ist.

Vertauscht man in einer gegebenen Matrix A = ( a ij ) 2 I R ⁿⁿ die Zeilen und Spalten mit Mit diesen Hauptdiagonalelemente unver andert

einer Permutation 2 S n durch A = ( a ij ) ;! A = ( a (i)(j) ), so bleibt die Menge der

fa 11 a 22 : : : a nn g = fa (1)(1) a (2)(2) : : : a (n)(n) g :

Uberlegungen l aat sich eine recht simple untere Schranke zu einem gegebenen a d i = a ii 1 i n

QAP bestimmen. Die Hauptdiagonalelemente der Matrizen A und B fasse man zu Vektoren

a ^d b ^d 2 I R ⁿ zusammen durch

b d i = b ii 1 i n

Da sich die Elemente der Hauptdiagonalen nach A n wendung einer Permutation nicht andern, ur ein gegebenes QAP, indem einerseits die Diagonaleintr age

Der Vektor a l aat sich i n O(n log n) sortieren (siehe 8] S. 163 .) erh alt man eine untere Schranke f

KAPITEL 2. L OSUNGSMETHODEN 12

der beiden Matrizen am kosteng unstigsten miteinander verrechnet werden und zum anderen der Rest der Eintr age der Matrizen A und B. ur den i-ten Zeilenvektor aus dem I R ⁿ Wir f uhren die Bezeichnung A i = ( a i1 a i2 ::: a in ) f

einer Matrix A ein. Der Vektor A ⁰ i bezeichnet den Vektor aus dem I R ^n;1 , der durch Streichen des Elementes a ii aus A i hervorgeht. F ur die Formulierung des ersten Satzes zur Bestimmung einer unteren Schranke fassen wir die Zeilen der Matrizen A und B ohne die jeweiligen Diagonalelemente zu Vektoren des I R n ^{2 ;n} zusammen

a ⁰ := (A ⁰ 1 A ⁰ 2 :::: A ⁰ n ) 2 I R n ² ;n

2 :::: B 0

l aat sich eine untere Schranke eines QAPs mit Matrizen AA B 2 I R ⁿⁿ bestimmen.

Satz 2.3 Durch

LB(QAP(AA B)) = < a ⁰ b ⁰ > ; + < a ^d b ^d > ^; Beweis. Es ist zu zeigen, daa diese Schranke den optimalen Zielfunktionswert von unten P a ij b (i)(j) n n 2Sn n n 2Sn i=1 a ii b (i)(i) + i=1 ann ahert.

min

2 Beispiel 2.1 Ein QAP der Dimension 4 mit zwei symmetrischen Matrizen AA B 2 I R ⁴⁴ sei A := 7 2 7 5 und B := 5 7 12 3 B B B B @ B B B B @

gegeben.

: Durch Zusammenfassen bzw. Streichen der Hauptdiagonalelemente erhalten wir die ben otigten

2.2. GILMOUR-LAWLER-BOUND (GLB) 13

a ⁰ = ( 3 6 7 3 5 2 6 5 7 7 2 7) und a ^d = ( 1 3 4 5) sowie

und damit ist

LB = 2 (2 12) + 4 (3 7) + 4 (5 6 ) + 2 (2 7) = 280

Der optimale Wert der Zielfunktion ist Z(AA B 0 ) = 324 mit optimaler Permutation

2. 0 = ( 1 4 2 3)

In dem Beispiel 2.1 ist der erreichte Wert der unteren Schranke trotz der geringen Dimension des Problems mit 86% nicht s e h r d i c ht an dem tats achlichen Wert. Es ist aufgrund der Konstruktion dieser Schranke zu erwarten, daa ihr Wert mit zunehmender Dimension immer mehr

von der optimalen L osung des QAPs a b weicht. Weil wir an besseren Schranken interessiert sind, ist es n otig, ein anderes Verfahren zu nden, daa m oglichst in polynomialer Zeit eine sch arfere untere Schranke liefert.

2.2 Gilmour-Lawler-Bound (GLB)

Eine sehr schnell zu berechnende Methode zum Auunden einer unteren Schranke zu einem

gegebenen QAP ist diejenige, die auf Gilmour und Lawler zur uckgeht. Dabei greifen wir zur Berechnung minimaler und maximaler Skalarprodukte auf den Satz 2.2 zur uck. Mit Hilfe der

Vektoren A ⁰ i und B ⁰ j i j = 1 : : : n(siehe voriger Abschnitt) deenieren wir uns eine Matrix L = ( l ij ) iij=1::::n 2 I R ⁿⁿ mit

l ij := a ii b jj + < A ⁰ i B ⁰ j > ; ii j = 1 :::: n (2.1)

Damit formuliert man den

Satz 2.4 Die L osung des linearen Zuordnungsproblems mit der unter (2.1) deenierten Matrix L = ( l ij ) iij=1::::n liefert die untere S c h r anke (Gilmour-Lawler-Bound) GLB(A, B) zu gegebenem QAP(A,B) mit X n

GLB(AA B) = min l i i (i)

2Sn i=1

Beweis. Zu zeigen ist, daa die angegebene Schranke den optimalen Zielfunktionswert von unten ann ahert.

KAPITEL 2. L OSUNGSMETHODEN 14

P

ⁿ GLB(AA B) = min l ^{i i} 1 (i)

1 ^{2Sn i=1} a ii b 1 ⁽ⁱ⁾ 1 (i) + < A ⁰ i B 0 P

2 Beispiel 2.2 Man berechne die GLB(AA B) zum gegebenen QAP aus Beispiel 2.1. Mit den

L = 108 85 64 123 B B B B @

C C C C A und l ost das lineare Z u o r dnungsproblem. Als optimale L osung und damit untere S c h r anke des Problems erh alt man GLB(AA B) = 317 mit Permutation 0 = ( 1 4 2 3). Die L osung der

mit optimalem Wert Z(AA B 0 ) = 324 dar. unteren Schranke stellt in diesem Beispiel bereits die optimale L osung des zugeh origen QAPs

2 Innerhalb des Branch&Bound-Algorithmus' in Abschnitt 2.4 werden immer wieder lineare Zuordnungsprobleme zur Bestimmung unterer Schranken gel ost. Danach soll jeweils die reduzierte Kostenmatrix gespeichert werden, die nach Addition bzw. Subtraktion der Dualvariablen beim Algorithmus von Tomizawa e n tsteht (siehe 23]). In dem Beispiel erg abe sich die L = 24 16 0 26 B B B B @

reduzierte Matrix gerade zu

2.3. VERGLEICH ALLER ZUL ASSIGEN L

OSUNGEN 15 wir im nachfolgenden ein null uberdeckendes System. D. h., daa dort mit der Optimall osung

Das durch diese Operationen entstandene System aus Nullen (durch gerahmt) nennen Anhand der Beweise der S atze 2.3 und 2.4 l aat sich s c hnell erkennen, daa die Gilmour-Lawler-

2 S n gerade l ii (i) = 0 i = 1 : : : n ist.

Schranke ( GLB) s c h arfer ist, als die erste bestimmte einfache untere Schranke LB. 2.3 Vergleich aller zul assigen L osungen Im allgemeinen Fall wird der L osungsraum der quadratischen Zuordnungsprobleme der Dimension n durch die symmetrische Gruppe S n der Ordnung n aufgespannt. Das bedeutet, daa es entsprechend den n! Elementen dieser Gruppe ebensoviele zul assige L osungen gibt. Man erkennt daran sehr leicht, daa das Probieren aller L osungen mit der Dimension der Probleme exponentiell w achst. Durchl auft man allerdings nacheinander alle Permutationen der L ange n, s o k ann man dadurch nicht n ur eine, sondern alle optimalen L osungen durch V ergleich der jeweiligen Zielfunktionswerte erhalten. Aufgrund des exponentiellen Wachstums der An-

zahl der L osungen stellt der Vergleich aller zul assigen L osungen kein geeignetes Werkzeug zur L osung gr ooerer QAPs dar (ab einer Gr ooe n > > 10 nicht mehr akzeptabel). Zum Test dieser Methode wurde ein Backtracking-Algorithmus (C -Routine siehe Abbildung 2.1) zur Erzeugung der Permutationen der L ange n implementiert. Auuerdem wurden zuf allige PC mit 32 MByte Arbeitsspeicher getestet. Die Testreihe ergab, daa sich Probleme bis n = 1 0 Testdaten mit steigender Dimension erzeugt. Die Probleme wurden auf einem Pentium/200

Zeitaufwand bereits im Stundenbereich. Die Ergebnisse entnehme man der Tabelle 2.1.

12 > 2h

KAPITEL 2. L 16

OSUNGSMETHODEN

void perm(int *val, int k, int n, int id){ int tt id+++ vallk]=idd

if(id==n){ /* Hier wurde eine neue Permutation *val aufgebaut */ } for(t=11t<=nnt++) if(vallt]==0) perm(val,t,n,id)) id---vallk]=00 returnn

}

Abbildung 2.1: C -Routine zur Erzeugung aller Permutationen der L ange n

2.4 Ein Branch & Bound-Algorithmus zur exakten L osung

quadratischer Zuordnungsprobleme

2.4.1 Vor uberlegungen Das hier vorgestellte Branch&Bound-Verfahren geht auf die St orungsmethode aus einem Artikel von R. E. Burkard zur uck (siehe 1]). In diesem Artikel wird zun achst ein Verfahren zur L osung allgemeiner quadratischer Zuordnungsprobleme und im weiteren ein Algorithmus f ur Koopmans-Beckmann-Probleme vorgestellt, der hier behandelt wird. Ein QAP der Form (1.1) mit den Matrizen A = ( a ij ) B = ( b ij ) C = ( c ij ) 2 I R ⁿⁿ sei gegeben. F ur die Konstruktion eines Branch&Bound-Algorithmus' sind nun zwei Regeln festzulegen. Zum einen muu ein Verfahren zur Bestimmung oberer und unterer Schranken

(Bounds) gew ahlt werden und zum anderen eine Verzweigungsregel (Branching). Bevor wir mit der Einf uhrung des Verfahrens der St orungsmethode beginnen, schauen wir ^{n n n} Z(AA B C ) = i=1 a ij b (i)(j) +

uns die zu minimierende Zielfunktion j=1 i=1 X X X

c i i ⁽ⁱ⁾ etwas genauer an. Anhand des Aufbaus erkennt man schnell, daa sich das Problem in zwei Bausteine unterteilt. Dabei bildet die erste Doppelsumme den quadratischen Teil und die zweite Summe den linearen Teil der Zielfunktion. Das heiit, daa sich das Problem in O(n ³ ) l osen lieee, wenn der quadratische Teil verschw ande und damit nur noch ein lineares Zuordnungsproblem zu l osen w are (siehe L osung linearer Zuordnungsprobleme in 23]). Zu Beginn des Verfahrens wollen wir das Ausgangsproblem so transformieren, daa m oglichst viele Informa-

2.4. EIN BRANCH&BOUND-ALGORITHMUS 17

werden kann, sollen die Matrizen A und B des Problems um Anteile reduziert werden, die zum linearen Teil der Zielfunktion addiert werden. Im g unstigsten Fall kann erreicht w erden, daa sich das Problem dadurch auf ein lineares Zuordnungsproblem reduziert, und eine L osung

in O(n ³ ) gefunden werden kann (siehe Abschnitt 2.4.2). Wir werden mit ~ a ij ) 2 I R ⁿⁿ A = ( ~

B = ( ~ b ij ) 2 I R ⁿⁿ die Matrizen bezeichnen, die durch Reduktion aus A und B hervor-und ~ gehen. Ebenso wird mit ~ c ij ) 2 I R ⁿⁿ die Matrix bezeichnet, die durch Aufaddieren C = ( ~

linearer Anteile der Matrizen A und B aus C hervorgeht. Damit erhalten wir zun achst ein modiiziertes Problem mit neuen Matrizen ~ A, ~ B, ~ C 2 I R nn

X X X ^{n n n} ~ a ij ~ b (i)(j) + c i i (i) : min ~ (2.2)

2Sn i=1 j=1 i=1

Der minimale Wert des linearen Anteils l aat sich durch L osen eines linearen Zuordnungsproblems mit entsprechender Kostenmatrix ~ C exakt bestimmen. Den Wert s des reduzierten quadratischen Anteils unter gegebener Zuordnung 2 S ⁿ X X n n

bezeichnet man als St orung, w oher das Verfahren seinen Namen bekommen hat. Am Anfang

des Verfahrens l ost man das lineare Zuordnungsproblem mit Kostenmatrix ~ C. A l s L osung

erh alt man den Optimalwert z mit der f ur das lineare Problem optimalen Zuordnung z . Danach wird der Wert der St orung unter der Zuordnung z berechnet. Ist der Wert der St orung bereits Null, so hat man eine optimale L osung des QAPs erhalten und kann abbrechen. Anderenfalls wird die Zuordnung z festgehalten und eine obere Schranke z des Problems bestimmt durch

z = z + s :

Danach m uu nun ein Verzweigungsschrittverfahren angewendet werden, um der Optimall osung n aher zu kommen oder zu zeigen, daa keine bessere L osung existiert.

2.4.2 Obere und untere Schranken

Im Laufe des Verfahrens werden verschiedene L osungen des gegebenen QAPs mit Zielfunktionswert z bestimmt. Der Wert der bislang besten L osung wird als obere Schranke z mit entsprechender Zuordnung z festgehalten.

Zur Bestimmung unterer Schranken soll das Ausgangsproblem auf ein kleineres quadratisches Problem mit erh ohtem linearen Anteil transformiert werden. Dabei m ochte man erreichen, daa der Wert der unteren Schranken m oglichst gut ist, also die verbleibenden Eintr age im reduzierten quadratischen Teil entsprechend klein werden. Auuerdem soll die Zuordnung, die zusammen mit einer unteren Schranke bestimmt wird, gleichzeitig einen Wert f ur eine obere

KAPITEL 2. L 18

OSUNGSMETHODEN Schranke liefern. Letzteres erreicht man gerade durch Erh ohung des linearen und Reduzierung

des quadratischen Anteils der Zielfunktion.

Reduktionsschemata des Ausgangsproblems Nach einigen

Uberlegungen (siehe auch Ausf uhrungen in 4]) l aat sich die Zielfunktion eines

gegebenen QAPs u m s c hreiben. Es k onnen nun zwei F alle auftreten.

1. Seien AA B 2 I R ⁿⁿ beliebig, so reduziere die beiden Matrizen A und B nach dem Schema, das hier f ur die Matrix A gegeben ist.

2. Falls eine der Matrizen symmetrisch ist, so verfahre mit den Reduktionen wie hier angegeben. Sei f ur das folgende o.B.d.A. B symmetrisch. Zerlege die Matrix A in vier Matrizen ~

AA A ^d A ^r und A ^c 2 I R ⁿⁿ . Die Matrix ~ A ist die Matrix, die im reduzierten Problem (2.2) verbleibt. Die Matrix A ^d enth alt die Eintr age der Hauptdiagonalen der Matrix A. A ^r entsteht durch die Berechnung der Zeilenminima und A ^c durch

Zun achst berechnet man die Matrix A d

A ^d = (a d ij ) a d ij := < anschlieeende Berechnung der Spaltenminima der Matrix A auuerhalb der Hauptdiagonalen. a ii falls i = j 0 sonst 8 :

ii j = 1 : : : n :

F ur das Aufstellen der Matrix A ^r bezeichnen wir mit p 2 I R ⁿ den Vektor der Zeilenminima ^1jn j6 =i und der Matrix A auuerhalb der Hauptdiagonalen. Damit ist p i := min a ij i = 1 :::: n ( p i falls i 6 = j 0 sonst A ^r = (a r ij ) a r ij :=

ii j = 1 : : : n : Man zieht jetzt die Eintr age der Matrix A ^r von denen der Matrix A ab. Danach berechnet

i6 =j man die Matrix A ^c durch Bestimmung der Spaltenminima der reduzierten Matrix A auuerhalb 1in und der Hauptdiagonalen. Dazu bezeichnen wir mit q 2 I R ⁿ die zu bestimmenden Spaltenminima q j := min (a ij ; p i ) j = 1 : : : n A ^c = (a c ij ) a c ij := 0 sonst ( q j falls i 6 = j

ii j = 1 : : : n : Schlieelich erh alt man durch diese Zerlegungen die Matrix ~ A = ( ~

2.4. EIN BRANCH&BOUND-ALGORITHMUS 19

~ A ij = A ij ; A d ij ; A r ij ; A c ij

Damit l aat sich die Zielfunktion umschreiben in

X X X n n n

(2.3)

Aufgrund der besonderen Eigenschaften der Matrizen A ^d A ^r und A ^c lassen sich die letzten

drei Summen der Gleichung (2.3) umformen.

Da A ^d nur die Eintr age der Hauptdiagonalen der Matrix A enth alt, folgt

P P P ^{n n n} a d ij b (i) (j) = a d ii b (i)(i) :

i=1 j=1 i=1

Die Matrix A ^r besteht n ur aus den jeweiligen Zeilenminima p i der Matrix A, also gilt

P P P P P P n n n n n n

Die Matrix A ^c enth alt die jeweiligen Spaltenminima nach Abzug der Zeilenminima, und

es ist

P P P P P P n n n n n n

KAPITEL 2. L 20

OSUNGSMETHODEN F ur jede m ogliche Zuordnung eines Indexes i zu einem Index j ergibt sich aus den letzten

vier Summen, siehe (2.3), eine Erh ohung des linearen Anteils. Die Koeezienten der Matrix ~ C = ( ~ c ij := c ij + a d ii b jj + p i s6 =j ~ s=1

z=1

b zj ii j = 1 : : : n : X z6 ⁼ⁱ n

j=1

j6 =i

~ a ij b (i)(j) (2.4)

l aat sich w eiter reduzieren, indem die Matrix B ahnlich der Matrix A in vier Matrizen ~

BB B ^d B ^r B ^c 2 I R ⁿⁿ zerlegt wird. Dabei ist B ^d gerade die Matrix der Hauptdiagonalelemente der Matrix B und ~

B die Matrix des reduzierten Problems (2.2). Es ist an dieser A bereits nur noch Nulleintr age auf der Hauptdiagonalen besitzt. Da eine beliebige Permutation den Hauptdiagonalelementen der Matrix ~ A wiederum

Hauptdiagonalelemente der Matrix B zuordnet, kann die Matrix B ^d vernachl assigt werden. Die Symmetrieeigenschaft der Matrix B soll sich auf die Matrix ~

B vererben. Dies gelingt,

indem iterativ die Zeilen- und Spaltenminima der Matrix B berechnet werden und in jedem Schritt der Iteration das jeweilige Minimum abgezogen wird. Dadurch erreichen wir, daa die Matrizen B ^r und die Transponierte der Matrix B ^c gleich sind.

F ur das Aufstellen der Matrizen B ^r und B ^c bezeichnen wir mit r 2 I R ⁿ den Vektor der ge-

b ji := b ij

:

j = 1 :::: n B ^r = ( b r ij ) B ^c = ( b c ij ) mit b r ij := b c ji :=

Danach lassen sich die Matrizen B ^r und B ^c aufstellen durch ( r i falls i 6 = j : ⁿ j6 =i ⁿ j=1 ⁿ j6 =i n

0 sonst achst j=1 a ij b (i)(j) = P ~ a ij ~ b (i) (j) + j=1 a ij b r (i) (j) +

ⁿ P P P n n n

Aus der Doppelsumme in (2.4) erhalten wir dadurch z u n ~ j6 =i ~ P P P P

i=1 i=1 i=1 i=1

j=1 j6 =i