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

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
• 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
• 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.