Approximationsalgorithmen - Exam

Aufgabe 1)

Du hast ein Optimierungsproblem in Form eines linearen Programms vorliegen. Die allgemeine Form des linearen Programms ist:

• Maximiere/Minimiere: \(c^T x\)
• Unter Nebenbedingungen: \(Ax \le b\), \(x \ge 0\)

Hierbei ist:

• \(x\) der Vektor der Entscheidungsvariablen
• \(c\) der Vektor der Zielfunktion
• \(A\) die Matrix der Nebenbedingungen
• \(b\) der Vektor der rechten Seite der Nebenbedingungen

a)

Teilaufgabe 1:

Gegeben sei folgendes lineares Programm:

Maximiere: \(3x_1 + 5x_2\)Unter den Nebenbedingungen:\(2x_1 + 3x_2 \le 12\)\(x_1 + x_2 \le 4\)\(x_1 \ge 0, \, x_2 \ge 0\)

Formuliere dieses Optimierungsproblem in der allgemeinen Form und bestimme die Lösungsmenge.

Lösung:

Um das gegebene lineare Programm in die allgemeine Form zu bringen, müssen wir die einzelnen Bestandteile zuordnen:

• Zielfunktion: Maximiere: \(3x_1 + 5x_2\)

• Nebenbedingungen:\(2x_1 + 3x_2 \le 12\)
• \(x_1 + x_2 \le 4\)
• \(x_1 \ge 0\)
• \(x_2 \ge 0\)

In der allgemeinen Form sieht das dann so aus:

• Maximiere c^T x, wobei c = \(\begin{pmatrix} 3 \ 5 \ \end{pmatrix}\)
• Unter den Nebenbedingungen:A = \(\begin{bmatrix} 2 & 3 \ 1 & 1 \ \end{bmatrix}\), und b = \(\begin{pmatrix} 12 \ 4 \ \end{pmatrix}\)
• und x = \(\begin{pmatrix} x_1 \ x_2 \ \end{pmatrix}\) mit x \ge 0

Bestimmung der Lösungsmenge:Um die Lösungsmenge zu bestimmen, verwenden wir die lineare Programmierungsmethode, beispielsweise das Simplex-Verfahren oder die grafische Lösung. Hier zeigen wir die grafische Lösung.

Wir zeichnen die Ungleichungen in einem Koordinatensystem:

• \(2x_1 + 3x_2 \le 12\)
• \(x_1 + x_2 \le 4\)
• \(x_1 \ge 0\)
• \(x_2 \ge 0\)

Diese Ungleichungen definieren ein Polygon im ersten Quadranten. Die Eckpunkte dieses Polygons, die durch die Schnittpunkte der Geraden entstehen, sind:

• \((0, 0)\)
• \((0, 4)\)
• \((6, 0)\)
• \((1.5, 2.5)\)

Wir berechnen den Zielfunktionswert \(3x_1 + 5x_2\) an jedem Eckpunkt:

• \((0, 0): 3(0) + 5(0) = 0\)
• \((0, 4): 3(0) + 5(4) = 20\)
• \((6, 0): 3(6) + 5(0) = 18\)
• \((1.5, 2.5): 3(1.5) + 5(2.5) = 16.5\)

Der höchste Wert ist 20, erreicht bei \((0, 4)\).

Daher ist die optimale Lösung:

• \(x_1 = 0\)
• \(x_2 = 4\)
• Mit Zielfunktionswert \(= 20\).

b)

Teilaufgabe 2:

Zeige, dass das duale Problem dieses linearen Programms ebenfalls ein lineares Programm ist. Formuliere hierfür das duale Problem und bestimme dessen allgemeine Form.

• Hinweis: Betrachte das allgemein duale Problem zur Maximierung:

Minimiere: \(b^T y\)Unter den Nebenbedingungen:\(A^T y \ge c\)\(y \ge 0\)

Hierbei ist \(y\) der Vektor der dualen Variablen.

Lösung:

Um zu zeigen, dass das duale Problem eines linearen Programms ebenfalls ein lineares Programm ist, müssen wir das duale Problem formulieren und seine allgemeine Form bestätigen.

Wir beginnen mit dem gegebenen primären Problem:

• Maximiere: \(3x_1 + 5x_2\)
• Unter den Nebenbedingungen: \(2x_1 + 3x_2 \le 12\), \(x_1 + x_2 \le 4\), \(x_1 \ge 0\), \(x_2 \ge 0\)

Die allgemeine Form des primären Problems ist:

• Maximiere: \(c^T x\)
• Unter den Nebenbedingungen: \(Ax \le b\), \(x \ge 0\)

Dies übersetzen wir in die konkrete Form:

• \(c = \begin{pmatrix} 3 \ 5 \ \end{pmatrix}\)
• \(A = \begin{bmatrix} 2 & 3 \ 1 & 1 \ \end{bmatrix}\)
• \(b = \begin{pmatrix} 12 \ 4 \ \end{pmatrix}\)

Nun zur Formulierung des dualen Problems:

• Das allgemein duale Problem zur Maximierung lautet:
• Minimiere: \(b^T y\)
• Unter den Nebenbedingungen: \(A^T y \ge c\), \(y \ge 0\)
• Hierbei ist \(y\) der Vektor der dualen Variablen.

In unserem Fall ist das duale Problem wie folgt:

• Minimiere: \(\begin{pmatrix} 12 & 4 \end{pmatrix} \begin{pmatrix} y_1 \ y_2 \ \end{pmatrix}\)
• Unter den Nebenbedingungen: \(\begin{bmatrix} 2 & 1 \ 3 & 1 \ \end{bmatrix} \begin{pmatrix} y_1 \ y_2 \ \end{pmatrix} \ge \begin{pmatrix} 3 \ 5 \ \end{pmatrix}\)
• \(y_1 \ge 0\)
• \(y_2 \ge 0\)

Dies übersetzen wir in die allgemein duale Form:

• Minimiere: \(b^T y\)
• Unter den Nebenbedingungen: \(A^T y \ge c\), \(y \ge 0\)

Dies zeigt, dass das duale Problem ebenfalls ein lineares Programm ist, da die Zielfunktion linear ist (Minimierung einer Linearkombination) und die Nebenbedingungen ebenfalls lineare Ungleichungen sind.

Aufgabe 2)

Simplex-Algorithmus und seine AnwendungenDer Simplex-Algorithmus, formuliert durch George Dantzig 1947, ist ein Verfahren zur Lösung linearer Optimierungsprobleme. Er arbeitet durch eine schrittweise Bewegung entlang der Kanten des zulässigen Bereichs zu einer optimalen Ecke. Dieses Verfahren kann sowohl für die Maximierung als auch für die Minimierung einer linearen Zielfunktion unter linearen Nebenbedingungen angewendet werden. Obwohl der Algorithmus im Durchschnitt effizient arbeitet, ist seine Worst-Case-Komplexität exponentiell. Zu den beliebten Anwendungen des Simplex-Algorithmus gehören Logistik, Produktionsplanung und Netzwerkflussprobleme.

a)

Gegeben sei das folgende lineare Optimierungsproblem: \[ \text{Maximiere } z = 3x_1 + 2x_2 \]\[ \text{unter den Nebenbedingungen: } \]\[ x_1 + x_2 \leq 4 \]\[ 2x_1 + x_2 \leq 5 \]\[ x_1, x_2 \geq 0\] wende den Simplex-Algorithmus an, um die optimale Lösung zu finden. Zeige die Schritte detailliert auf, einschließlich der Auswahl der Pivot-Elemente und der Berechnungen der neuen Tableau-Zeilen.

Lösung:

Simplex-Algorithmus zur Lösung des linearen Optimierungsproblems

Problemformulierung

Gegeben sei das lineare Optimierungsproblem:

• \( \text{Maximiere } z = 3x_1 + 2x_2 \)
• \( \text{unter den Nebenbedingungen: } \)
• \( x_1 + x_2 \leq 4 \)
• \( 2x_1 + x_2 \leq 5 \)
• \( x_1, x_2 \geq 0 \)

Um dieses Problem mit dem Simplex-Algorithmus zu lösen, führen wir die Schritte im Detail durch.

Schritt 1: Standardform des Problems

Erweitere das Problem durch Einfügen der Schlupfvariablen \( s_1 \) und \( s_2 \), um die Gleichungen zu erhalten:

• \( x_1 + x_2 + s_1 = 4 \)
• \( 2x_1 + x_2 + s_2 = 5 \)
• \( x_1, x_2, s_1, s_2 \geq 0 \)

Die Zielfunktion wird auch in die Standardform gebracht:

• \( z - 3x_1 - 2x_2 = 0 \)

Schritt 2: Initiales Tableau erstellen

Stellen wir das initiale Simplex-Tableau auf:

\begin{array}{c|cccc|c}  \text{Basis} & x_1 & x_2 & s_1 & s_2 &\text{RHS} \  \hline  s_1 & 1 & 1 & 1 & 0 & 4 \  s_2 & 2 & 1 & 0 & 1 & 5 \  \hline  z & -3 & -2 & 0 & 0 & 0 \  \end{array}  

Schritt 3: Pivot-Element auswählen

Wähle das Pivot-Element aus. Dies ist das Element in der Pivot-Spalte und Pivot-Zeile. Die Pivot-Spalte wird aus der Zielfunktion ausgewählt, indem wir die variable mit dem kleinsten Koeffizienten im Zielfunktionsbereich auswählen (hier -3 für \( x_1 \)).

Nun suchen wir die Pivot-Reihe durch Division der rechten Seite durch die Werte in der Pivot-Spalte und Auswahl der kleinsten positiven nicht-negativen Quote:

• \( \frac{4}{1} = 4 \)
• \( \frac{5}{2} = 2.5 \)

Daher ist die Pivot-Reihe die zweite Reihe. Das Pivot-Element ist 2 (\( x_1 \) Spalte und \( s_2 \) Zeile).

Schritt 4: Pivot-Operation durchführen

Teilen wir die Pivot-Reihe durch das Pivot-Element:

\begin{array}{c|cccc|c}  \text{Basis} & x_1 & x_2 & s_1 & s_2 &\text{RHS} \  \hline  s_1 & 1 & 1 & 1 & 0 & 4 \  s_2 (\text{Pivot}) & 1 & \frac{1}{2} & 0 & \frac{1}{2} & 2.5 \  \hline  z & -3 & -2 & 0 & 0 & 0 \  \end{array}  

Führen wir die Pivot-Operation auf die anderen Reihen des Tableaus durch (eliminiere die \( x_1 \) Spalte in anderen Zeilen):

\begin{array}{c|cccc|c}  \text{Basis} & x_1 & x_2 & s_1 & s_2 &\text{RHS} \  \hline  s_1 & 0 & \frac{1}{2} & 1 & -\frac{1}{2} & 1.5 \  x_1 & 1 & \frac{1}{2} & 0 & \frac{1}{2} & 2.5 \  \hline  z & 0 & \frac{1}{2} & 0 & \frac{3}{2} & 7.5 \  \end{array}  

Schritt 5: Weitere Pivot-Operationen durchführen

Da alle Einträge in der Zielfunktion jetzt nicht-negativ sind, haben wir das Optimum erreicht.

Die optimale Lösung ist:

• \( x_1 = 2.5 \)
• \( x_2 = 1.5 \)
• \( s_1 = 0 \)
• \( s_2 = 0 \)
• \( z = 7.5 \)

Dies ist die optimale Lösung des gegebenen linearen Optimierungsproblems. Der optimale Wert von \( z \) ist 7.5.

b)

Erkläre, warum der Simplex-Algorithmus in praktischen Anwendungen oft effizient ist, obwohl seine Worst-Case-Komplexität exponentiell sein kann. Diskutiere insbesondere, welche Eigenschaften von realen Problemen dazu beitragen, dass der Algorithmus effizient läuft.

Lösung:

Effizienz des Simplex-Algorithmus in praktischen Anwendungen

Obwohl der Simplex-Algorithmus theoretisch eine exponentielle Worst-Case-Komplexität hat, ist er in praktischen Anwendungen oft effizient. Im Folgenden werden einige Gründe und Eigenschaften von realen Problemen diskutiert, die dazu beitragen:

• Spezielle Struktur der ProblemeReale Probleme haben oft eine spezielle Struktur, die sie einfacher zu lösen macht. Beispielsweise können viele praktische Optimierungsprobleme in der Logistik oder Produktionsplanung eine bestimmte Regularität oder Symmetrie aufweisen, die der Simplex-Algorithmus ausnutzen kann.
• Schwache Worst-Case-SzenarienViele der Worst-Case-Szenarien des Simplex-Algorithmus sind künstlich und treten in der Praxis selten auf. Das bedeutet, dass der Algorithmus in den meisten realen Szenarien weit von seinem Worst-Case entfernt ist.
• Baserichtungen und Pivot-OperationenDer Simplex-Algorithmus bewegt sich entlang der Kanten der zulässigen Region und erreicht oft schnell eine optimale Ecke. Dies liegt daran, dass die Anzahl der Pivot-Operationen in wirklichen Anwendungen normalerweise klein bleibt, selbst wenn der Lösungsraum groß ist.
• Fortschritt zu besseren LösungenBei jeder Iteration des Simplex-Algorithmus wird die Zielfunktion verbessert oder bleibt gleich. In der Praxis führen diese schrittweisen Verbesserungen häufig sehr schnell zum Optimum.
• Fortschritt in der AlgorithmustechnologieModerne Implementierungen des Simplex-Algorithmus nutzen fortschrittliche Techniken und Heuristiken, die die Effizienz weiter verbessern. Dazu gehören Verbesserungen wie Dual-Simplex und der Einsatz von Initiallösungstechniken.
• Numerische StabilitätReale Anwendungen arbeiten oft mit numerischen Daten, die gut konditioniert sind und keine extremen Werte annehmen. Dies trägt zur Stabilität und Effizienz des Algorithmus bei.

Zusammenfassend lässt sich sagen, dass der Simplex-Algorithmus aufgrund der spezifischen Natur und Struktur vieler realer Probleme, gepaart mit algorithmischen Verbesserungen, in der Praxis oft viel effizienter ist als seine theoretische Worst-Case-Analyse vermuten lässt.

c)

Beschreibe eine praktische Anwendung des Simplex-Algorithmus in der Logistik und erläutere, wie der Algorithmus verwendet wird, um eine optimale Lösung für dieses Problem zu finden. Stelle sicher, dass Du mindestens ein reales Beispiel nennst und die Schritte des Algorithmus im Kontext des Beispiels beschreibst.

Lösung:

Praktische Anwendung des Simplex-Algorithmus in der Logistik

Der Simplex-Algorithmus wird in der Logistikbranche häufig verwendet, um verschiedene Optimierungsprobleme zu lösen. Ein typisches Beispiel ist die Optimierung der Transportwege (Transportproblem).

Beispiel: Minimierung der Transportkosten

Angenommen, ein Unternehmen möchte die Transportkosten minimieren, um Waren von mehreren Lagerhäusern zu verschiedenen Verkaufsstellen zu liefern. Die Kapazitäten der Lagerhäuser und der Bedarf der Verkaufsstellen sind bekannt, ebenso wie die Transportkosten pro Einheit zwischen jedem Lagerhaus und jeder Verkaufsstelle.

Problemstellung:

• Lagerhäuser: Lagerhaus A (Kapazität 20), Lagerhaus B (Kapazität 30)
• Verkaufsstellen: Verkaufsstelle 1 (Bedarf 10), Verkaufsstelle 2 (Bedarf 28), Verkaufsstelle 3 (Bedarf 12)
• Transportkosten: Die Kosten pro Einheit sind in der folgenden Tabelle dargestellt:

      Verkaufsstelle 1   Verkaufsstelle 2   Verkaufsstelle 3A            2                 4                 5B            3                 1                 7

Mathematische Formulierung

Sei \(x_{ij}\) die Anzahl der Einheiten, die vom Lagerhaus \(i\) zur Verkaufsstelle \(j\) transportiert werden. Das Ziel ist es, die Gesamttransportkosten zu minimieren:

• \( \text{Minimiere: } z = 2x_{A1} + 4x_{A2} + 5x_{A3} + 3x_{B1} + 1x_{B2} + 7x_{B3} \)
• \( \text{unter den Nebenbedingungen:} \)
• \( x_{A1} + x_{A2} + x_{A3} \leq 20 \) (Kapazität von Lagerhaus A)
• \( x_{B1} + x_{B2} + x_{B3} \leq 30 \) (Kapazität von Lagerhaus B)
• \( x_{A1} + x_{B1} = 10 \) (Bedarf der Verkaufsstelle 1)
• \( x_{A2} + x_{B2} = 28 \) (Bedarf der Verkaufsstelle 2)
• \( x_{A3} + x_{B3} = 12 \) (Bedarf der Verkaufsstelle 3)
• \( x_{ij} \geq 0 \text{ für alle } i,j \)

Anwendung des Simplex-Algorithmus

Schritt 1: Standardform des Problems

Fügen wir Schlupfvariablen \( s_1, s_2, s_3, s_4 \) hinzu, um die Ungleichungen in Gleichungen umzuwandeln:

• \( x_{A1} + x_{A2} + x_{A3} + s_1 = 20 \)
• \( x_{B1} + x_{B2} + x_{B3} + s_2 = 30 \)
• \( x_{A1} + x_{B1} = 10 \)
• \( x_{A2} + x_{B2} = 28 \)
• \( x_{A3} + x_{B3} = 12 \)

Die Zielfunktion wird zu:

• \( z - 2x_{A1} - 4x_{A2} - 5x_{A3} - 3x_{B1} - 1x_{B2} - 7x_{B3} = 0 \)

Schritt 2: Initiales Tableau erstellen

Aufstellen des initialen Simplex-Tableaus:

\begin{array}{c|ccccccc|c}  \text{Basis} & x_{A1} & x_{A2} & x_{A3} & x_{B1} & x_{B2} & x_{B3} & s_1 & s_2 & s_3 & s_4 &\text{RHS} \  \hline  s_1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 20 \  s_2 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 30 \  x_{A1} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 10 \  x_{A2} & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 28 \  x_{A3} & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 12 \  \hline  z & -2 & -4 & -5 & -3 & -1 & -7 & 0 & 0 & 0 & 0 & 0 \  \end{array}  

Schritt 3: Pivot-Element auswählen

Wähle das Pivot-Element basierend auf der Vorstellung, die Variable in das Basis zu bringen, die die größte Verbesserung bringt (die Spalte mit dem größten negativen Koeffizienten in der Zielfunktion wählen). Führe dann die Pivot-Operationen durch, bis alle Koeffizienten in der Zielfunktion nicht-negativ sind.

Schritt 4: Weitere Pivot-Operationen

Iteriere den Prozess, wähle Pivotelemente, bis alle \textit{Kosten - Koeffizienten} nicht-negative sind.

Ergebnis

Die optimale Lösung des Problems wird durch das endgültige Simplex-Tableau bereitgestellt. Die minimalen Transportkosten werden durch die RHS der Zielfunktion dargestellt, und die Transportmengen werden durch die Werte in den nicht-Schlund-Vergleichsvariablen dargestellt.

In der Praxis liefert der Simplex-Algorithmus eine systematische Methode, um diese optimale Lösung effizient zu ermitteln, indem er schrittweise entlang der Kanten des zulässigen Bereichs zu einer optimalen Ecke fortschreitet.

Ein reales Beispiel aus der Praxis wäre die Optimierung der Lieferwege und -mengen für ein Supermarktnetzwerk, das aus mehreren Lagern und vielen Filialen besteht. Der Simplex-Algorithmus wird genutzt, um die Transportkosten zu minimieren, dabei die Kapazitäten der Lager und die Nachfrage der Filialen zu berücksichtigen.

Aufgabe 3)

Der Branch-and-Bound-Algorithmus ist ein Ansatz zur Lösung von Optimierungsproblemen, der durch systematisches Durchsuchen des Lösungsraums und Abschneiden nicht vielversprechender Teillösungen funktioniert. Er zerlegt das Problem in Teillösungen (Branching) und setzt Schranken (Bounding) zur Bewertung dieser Teillösungen. Bei ungünstigen Schranken erfolgt das Abschneiden (Pruning) unwirtschaftlicher Suchpfade. Typische Anwendungsbereiche sind das Rucksackproblem, das Traveling Salesman Problem und gemischt-ganzzahlige lineare Programme (MILP).

a)

a) Beschreibe die Schritte des Branch-and-Bound-Algorithmus bei der Lösung eines Rucksackproblems. Betrachte ein Rucksackproblem mit folgenden Gegenständen:

• Gegenstand A: Wert 60, Gewicht 10
• Gegenstand B: Wert 100, Gewicht 20
• Gegenstand C: Wert 120, Gewicht 30

Der Rucksack hat eine maximale Tragfähigkeit von 50. Führe die ersten beiden Schritte des Branching und Bounding durch und gib alle Zwischenschritte inklusive Schranken und Pruning an.

Lösung:

a) Beschreibe die Schritte des Branch-and-Bound-Algorithmus bei der Lösung eines Rucksackproblems. Betrachte ein Rucksackproblem mit folgenden Gegenständen:

• Gegenstand A: Wert 60, Gewicht 10
• Gegenstand B: Wert 100, Gewicht 20
• Gegenstand C: Wert 120, Gewicht 30

Der Rucksack hat eine maximale Tragfähigkeit von 50. Führe die ersten beiden Schritte des Branching und Bounding durch und gib alle Zwischenschritte inklusive Schranken und Pruning an.

Lösung:

1. Initialisierung: Der Algorithmus startet mit einem Knoten auf der Wurzelebene, wobei der Knoten den gesamten verfügbaren Platz und das gesamte ungenutzte Potenzial darstellt. Die initiale Schranke kann hier als 'Upper Bound' (UB) bezeichnet werden. Diese UB stellt den maximal möglichen Wert dar, den wir erreichen können, wenn wir alle Gegenstände mitnehmen können. UB = 60 (A) + 100 (B) + 120 (C) = 280 Die aktuelle Lösung (Current Solution, CS) hat zu Beginn einen Wert von 0 und ein Gewicht von 0.
2. Erster Schritt des Branching: Wir beginnen mit Gegenstand A. Es gibt zwei Möglichkeiten: Wir nehmen ihn (1) oder nehmen ihn nicht (0).
   • Knoten 1: Wir nehmen Gegenstand A. CS: Wert = 60, Gewicht = 10 Restkapazität = 50 - 10 = 40 UB für diesen Knoten: 60 (A) + 100 (B) + 120 (C) = 280 Die UB bleibt 280, weil wir theoretisch immer noch alle Gegenstände B und C aufnehmen können.
   • Knoten 2: Wir nehmen Gegenstand A nicht. CS: Wert = 0, Gewicht = 0 Restkapazität = 50 UB für diesen Knoten: 100 (B) + 120 (C) = 220 Die UB sinkt hier auf 220, da der Wert von Gegenstand A nicht mehr mitgezählt wird.
3. Pruning (Erster Schritt): Beide Knoten werden vorerst nicht abgeschnitten, da sie weiterhin vielversprechend sind.
4. Zweiter Schritt des Branching: Wir betrachten nun Knoten 1 und führen erneut das Branching durch, dieses Mal für Gegenstand B. Wieder gibt es zwei Möglichkeiten: Nehmen oder nicht nehmen.

• Knoten 1.1: Wir nehmen Gegenstand B (und haben bereits A). CS: Wert = 60 (A) + 100 (B) = 160 Gewicht = 10 (A) + 20 (B) = 30 Restkapazität = 50 - 30 = 20 UB für diesen Knoten: 160 (A und B) + 120 (C) = 280. Dieser Knoten bleibt vielversprechend.
• Knoten 1.2: Wir nehmen Gegenstand B nicht (aber haben A). CS: Wert = 60 Gewicht = 10 Restkapazität = 40 UB für diesen Knoten: 60 (A) + 120 (C) = 180. Dieser Knoten sinkt auf eine UB von 180.
• Knoten 2.1: Wir nehmen Gegenstand B (Wir haben A nicht genommen). CS: Wert = 100 Gewicht = 20 Restkapazität = 30 UB für diesen Knoten: 100 (B) + 120 (C) = 220.
• Knoten 2.2: Wir nehmen Gegenstand B nicht (Wir haben A nicht genommen). CS: Wert = 0 Gewicht = 0 Restkapazität = 50 UB für diesen Knoten: 120 (C) = 120.

Pruning (Zweiter Schritt): Knoten 2.2 kann bereits abgeschnitten werden, weil seine UB (120) niedriger ist als die beste gefundene Lösung (160 aus Knoten 1.1).

b)

b) Erkläre, wie die oberen und unteren Schranken im Branch-and-Bound-Algorithmus gesetzt werden können. Gib ein Beispiel einer oberen Schranke für ein Traveling Salesman Problem, wenn die aktuelle Teillösung folgende Knoten bereits enthält: A → B → C. Verwende beliebige plausible Kantenkosten.

Lösung:

b) Erkläre, wie die oberen und unteren Schranken im Branch-and-Bound-Algorithmus gesetzt werden können. Gib ein Beispiel einer oberen Schranke für ein Traveling Salesman Problem, wenn die aktuelle Teillösung folgende Knoten bereits enthält: A → B → C. Verwende beliebige plausible Kantenkosten.

Lösung:

Im Branch-and-Bound-Algorithmus sind die oberen und unteren Schranken entscheidend für die Bewertung der Teillösungen:

• Obere Schranke (Upper Bound, UB): Dies ist die beste gefundene Lösung oder eine Schätzung des maximal möglichen Wertes, den wir durch vollständiges Durchlaufen eines Suchpfades erreichen können. Im Fall von Maximierungsproblemen stellen wir anfangs die UB als Summe der maximal möglichen Werte auf. Für Minimierungsprobleme (wie das Traveling Salesman Problem), stellen wir eine UB als Schätzung der Gesamtkosten des kürzesten Pfades auf.
• Untere Schranke (Lower Bound, LB): Dies ist die beste aktuell bekannte Lösung. Bei Optimierungsproblemen aktualisieren wir diese Schranke regelmäßig, wenn wir neue, besser Lösungen finden. Bei Minimierungsproblemen ist dies die aktuelle niedrigste gefundene Lösung.

Für das Traveling Salesman Problem (TSP) ist das Ziel, den kürzesten Rundweg zu finden, der alle Städte genau einmal besucht und zum Ausgangspunkt zurückführt.

Nehmen wir an, wir sind derzeit in einer Teillösung, die die Knoten A → B → C enthält, und wir verwenden ein Beispiel für beliebige Kantenkosten:

• Kosten von A nach B: 10
• Kosten von B nach C: 15
• Kosten von A nach C: 20
• Kosten von B nach D: 25
• Kosten von C nach D: 30

1. Die aktuelle Teillösung hat Kosten: 10 (A→B) + 15 (B→C) = 25.

2. Um eine Obergrenze (UB) für diese Teillösung zu setzen: Wir müssen eine Schätzung der minimalen zusätzlichen Kosten machen, die erforderlich sind, um diese Teillösung zu einem vollständigen Rundweg zu erweitern:

   • Kosten von C nach D: 30
   • Kosten von D nach A (zurück zum Startpunkt): 35

   Schätzung der Gesamtkosten für die vollständige Lösung: 25 (aktuelle Kosten) + 30 (C→D) + 35 (D→A) = 90.

   Also könnte eine plausible obere Schranke (UB) für diese Teillösung 90 sein. Dies schließt alle zusätzlichen Kantenkosten ein, die benötigt werden, um den Rundweg abzuschließen.

c)

c) Implementiere einen Pseudocode für den Branch-and-Bound-Algorithmus zur Lösung eines gemischt-ganzzahligen linearen Programms (MILP). Der Algorithmus sollte die Branching- und Bounding-Schritte sowie das Pruning der unwirtschaftlichen Pfade beinhalten.

Lösung:

c) Implementiere einen Pseudocode für den Branch-and-Bound-Algorithmus zur Lösung eines gemischt-ganzzahligen linearen Programms (MILP). Der Algorithmus sollte die Branching- und Bounding-Schritte sowie das Pruning der unwirtschaftlichen Pfade beinhalten.

Lösung:

Der Branch-and-Bound-Algorithmus für ein gemischt-ganzzahliges lineares Programm (MILP) kann in Pseudocode wie folgt beschrieben werden:

  // Pseudocode für Branch-and-Bound-Algorithmus zur Lösung eines MILPinitialize:  best_solution = None best_value = -∞  // Für Maximierungsproblem. Setze auf ∞ für Minimierungsproblem. nodes = Queue()  root = initial_problem()  nodes.enqueue(root) while not nodes.is_empty():  current_node = nodes.dequeue()  // 1. Solve the relaxed linear problem  solution = solve_linear_relaxation(current_node)  if solution is infeasible:  continue  // 2. Bounding  if solution.value > best_value:   // Check if solution is also integer feasible   if is_integer_feasible(solution):    best_solution = solution    best_value = solution.value   // Branching   else:    branching_variable = select_branching_variable(solution)    left_node = current_node.branch(branching_variable, direction='left')    right_node = current_node.branch(branching_variable, direction='right')    nodes.enqueue(left_node)    nodes.enqueue(right_node) return best_solution // Funktionen:function solve_linear_relaxation(node):  // Lösung des Linearen Relaxationsproblems // Rückgabe der Lösung mit Zielfunktionswertfunction is_integer_feasible(solution):  // Prüfen, ob die Lösung alle Ganzzahlanforderungen erfüllt // Rückgabe von True oder Falsefunction select_branching_variable(solution):  // Auswahl einer Variablen zum Branching, die nicht ganzzahlig ist // Rückgabe der Variablenfunction branch(node, variable, direction):  // Branching des Knotens nach links oder rechts // Rückgabe des neuen Knotens 

Erklärung der Hauptschritte:

• Initialisierung: Die besten bekannten Lösungen und Werte werden initialisiert, und der Wurzelknoten des Problems wird in die Warteschlange eingefügt.
• Relaxation lösen: Löst das entspannte lineare Problem für den aktuellen Knoten.
• Bounding: Vergleicht die Lösung mit der besten bekannten Lösung und aktualisiert diese gegebenenfalls.
• Branching: Bei nicht-ganzzahligen Lösungen wird eine Variable ausgewählt, und es werden neue Teillösungen durch Branching erzeugt.
• Pruning: Unwirtschaftliche Pfade (Knoten mit schlechterer Schranke) werden von vornherein nicht weiter verfolgt oder verworfen.

Aufgabe 4)

Context: Cutting-Plane-Methoden sind Optimierungsverfahren, die benutzt werden, um ganzzahlige lineare Programme (ILP) zu lösen. Ziel dieser Methoden ist es, die optimale Lösung schrittweise zu approximieren, indem iterativ Schnittebenen hinzugefügt werden. Diese Schnittebenen werden durch Ungleichungen definiert, die sicherstellen, dass keine ganzzahligen Punkte innerhalb des zulässigen Bereichs enthalten sind. Häufig genutzte Software-Tools für diese Methoden sind Cplex und Gurobi, insbesondere in Kombination mit Branch-and-Bound-Verfahren, bekannt als Branch-and-Cut.Ein weiterer wichtiger Faktor für die Effizienz dieser Methode ist die Wahl der Schnittebenen, wobei bekannte Beispiele für solche Schnitte Gomory-Schnitte und Chvátal-Gomory-Schnitte sind.

a)

Aufgabe: Beschreibe den allgemeinen Ablauf der Cutting-Plane-Methode zur Lösung eines ganzzahligen linearen Programms (ILP). Gehe dabei auf die Rolle der Schnittebenen und deren Auswahl ein.

Lösung:

Lösung:

• 1. Initiales Relaxieren: Der erste Schritt bei der Cutting-Plane-Methode besteht darin, das ganzzahlige lineare Programm (ILP) als lineares Programm (LP) zu relaxieren. Die Lösung dieses LPs ignoriert die Ganzzahligkeitsbeschränkungen und ermöglicht eine kontinuierliche Lösung.
• 2. Lösung des Relaxierten LPs: Nachdem das ILP relaxiert wurde, wird das resultierende LP mittels gängiger linearer Optimierungsmethoden, wie dem Simplex-Algorithmus, gelöst. Das Ergebnis ist eine Lösung, die innerhalb des zulässigen Bereichs für das LP liegt, jedoch nicht unbedingt ganzzahlig ist.
• 3. Überprüfung der Ganzzahligkeit: Die erhaltene Lösung wird geprüft, ob sie ganzzahlig ist. Ist dies der Fall, so ist diese auch eine zulässige Lösung des ursprünglichen ILPs und das Verfahren kann beendet werden. Ist die Lösung nicht ganzzahlig, muss eine Schnittebene eingeführt werden.
• 4. Erstellung der Schnittebene: Eine Schnittebene (Cutting Plane) ist eine Ungleichung, die zur bestehenden Menge von Beschränkungen hinzugefügt wird. Diese wird so konstruiert, dass sie die aktuelle, nicht-ganzzahlige Lösung ausschließt, jedoch keine der zulässigen ganzzahligen Lösungen des ILPs. Beispiele für solche Schnitte sind der Gomory-Schnitt und der Chvátal-Gomory-Schnitt.
• 5. Hinzufügen der Schnittebene: Die neu erzeugte Schnittebene wird zum LP hinzugefügt, wodurch das zulässige Gebiet eingeschränkt wird.
• 6. Wiederholung: Das erweiterte LP wird erneut gelöst, und der Prozess startet von neuem bei Schritt 2. Dies geschieht iterativ, bis entweder eine ganzzahlige Lösung gefunden wird, oder festgestellt wird, dass keine zulässige ganzzahlige Lösung existiert.
• Rolle der Schnittebenen: Die Schnittebenen sind entscheidend für die Cutting-Plane-Methode, da sie dazu beitragen, den Lösungssatz effizient auf die ganzzahligen Punkte einzuschränken. Die Auswahl der Schnittebenen beeinflusst maßgeblich die Effizienz des Verfahrens. Effiziente Schnittebenen sorgen dafür, dass große Teile des Suchraums ausgeschlossen werden, ohne gültige ganzzahlige Lösungen zu verlieren.
• Wahl der Schnittebenen: Die Wahl der Schnittebenen ist ein kritischer Aspekt und verschiedene Strategien können angewendet werden. Gomory-Schnitte basieren auf Lösungen der Duals und ermöglichen oft schnelle Fortschritte. Chvátal-Gomory-Schnitte sind eine Verallgemeinerung und bieten mehr Flexibilität. Die letztendliche Wahl hängt von der Struktur des Problems und der Implementierung in Software-Tools wie Cplex oder Gurobi ab.

c)

Implementierungsfrage: Implementiere einen simplen Algorithmus in Python, der eine Cutting-Plane-Methode mit Gomory-Schnitten für ein kleines ILP-Problems verwendet. Nutze hierfür eine geeignete Bibliothek wie z.B. PuLP oder ähnliches.

import pulp# Beispiel für ein ILP-Problem# Implementierung hier einfügen

Lösung:

Implementierungsfrage:Um die Cutting-Plane-Methode mit Gomory-Schnitten für ein kleines ILP-Problem in Python zu implementieren, verwenden wir die PuLP-Bibliothek. Hier ist ein einfacher Algorithmus, der dieses Verfahren demonstriert:

import pulpimport numpy as np# Funktion zur Lösung eines LPs und Rückgabe der Lösung und Basisvariablendef solve_lp(problem):    problem.solve()    status = pulp.LpStatus[problem.status]    solution = [v.varValue for v in problem.variables()]    return status, solution# Funktion zur Identifizierung nicht-ganzzahliger Variablendef get_fractional_indices(solution):    return [i for i, x in enumerate(solution) if not float(x).is_integer()]# Funktion zur Hinzufügung eines Gomory-Schnittsdef add_gomory_cut(problem, tableau, row_index):    row = tableau[row_index]    cut_expr = pulp.LpAffineExpression()    rhs_fraction = row[-1] - int(row[-1])    cut_expr += rhs_fraction    for j in range(len(row)-1):        coeff_fraction = row[j] - int(row[j])        cut_expr -= coeff_fraction * problem.variables()[j]            # Hinzufügen des Schnitts zur Problemdefinition    problem += cut_expr <= 0# Beispiel für ein ILP-Problem# minimize: 3x + y# subject to: 2x + 3y <= 12#             -x + 4y <= 8def cutting_plane_ilp():    problem = pulp.LpProblem('Example_ILP', pulp.LpMinimize)    # Variablen    x = pulp.LpVariable('x', lowBound=0, cat='Continuous')    y = pulp.LpVariable('y', lowBound=0, cat='Continuous')        # Zielfunktion    problem += 3*x + y    # Nebenbedingungen    problem += 2*x + 3*y <= 12    problem += -x + 4*y <= 8    # Iterativer Lösungsprozess    while True:        status, solution = solve_lp(problem)        frac_indices = get_fractional_indices(solution)        if len(frac_indices) == 0:            break        row_index = frac_indices[0]  # Nehme die erste nicht-ganzzahlige Variable        # Erzeuge das Simplex-Tableau (Nur zur Demonstration)        tableau = np.array([[2, 3, 12],                           [-1, 4, 8],                           [3, 1, solution[0]*3 + solution[1]]]) # Fiktiv letzte Zeile als Zielfunktion                                    add_gomory_cut(problem, tableau, row_index)    status, solution = solve_lp(problem)    print(f'Status: {status}')    print(f'Lösung: {solution}')cutting_plane_ilp()

Erklärung des Codes:

• solve_lp: Diese Funktion löst das gegebene LP-Problem und gibt den Status und die Lösung zurück.
• get_fractional_indices: Diese Funktion identifiziert die Indizes der Variablen mit nicht-ganzzahligen Werten in der Lösung.
• add_gomory_cut: Diese Funktion fügt dem LP-Problem einen Gomory-Schnitt hinzu, basierend auf dem aktuellen Simplex-Tableau und der nicht-ganzzahligen Basisvariable.
• cutting_plane_ilp: Diese Funktion definiert ein ILP-Problem, löst es iterativ unter Hinzufügung von Gomory-Schnitten, und gibt die erreichte ganzzahlige Lösung aus.

d)

Kritische Analyse: Diskutiere die Vor- und Nachteile der Cutting-Plane-Methode im Vergleich zu anderen Approximationsalgorithmen, die für die Lösung von ILPs verwendet werden. Gehe insbesondere auf die Kombination mit Branch-and-Bound und die Effizienz der Methode ein.

Lösung:

Kritische Analyse der Cutting-Plane-Methode:Die Cutting-Plane-Methode ist eine der etablierten Methoden zur Lösung von ganzzahligen linearen Programmen (ILPs). Sie funktioniert, indem iterativ Schnittebenen zu einem relaxierten linearen Programm hinzugefügt werden, um den Bereich der zulässigen Lösungen zu verbessern. Diese Methode hat sowohl Vorteile als auch Nachteile im Vergleich zu anderen Approximationsalgorithmen wie dem Branch-and-Bound-Verfahren. Im Folgenden werden die wichtigsten Aspekte diskutiert:

• Vorteile:
  • Effektive Einschränkung des Suchraums: Cutting-Plane-Methoden können den Suchraum effizient einschränken, indem sie durch Schnittebenen viele nicht-ganzzahlige Lösungen ausschließen. Dies kann besonders nützlich sein, wenn der zulässige Bereich sehr groß ist.
  • Verbesserte Relaxierungslösungen: Die Methode verbessert schrittweise die Lösung des relaxierten Problems und nähert sich dadurch der optimalen ganzzahligen Lösung an. Dies kann bei Problemen mit wenigen optimalen ganzzahligen Lösungen hilfreich sein.
  • Kombinierbarkeit mit anderen Methoden: Die Cutting-Plane-Methode lässt sich gut mit Branch-and-Bound zu einem Branch-and-Cut-Verfahren kombinieren. Diese Kombination profitiert von den Stärken beider Methoden und kann so oft schneller zu einer Lösung führen.
  • Flexibilität bei der Wahl der Schnitte: Es gibt verschiedene Arten von Schnittebenen (z.B. Gomory-Schnitte, Chvátal-Gomory-Schnitte), die je nach Problemstruktur gewählt werden können, um die Effizienz zu maximieren.
• Nachteile:
  • Rechenaufwand: Das wiederholte Lösen des LPs nach Hinzufügen jeder neuen Schnittebene kann rechenintensiv und zeitaufwändig sein. Insbesondere bei großen Problemen mit vielen Variablen und Restriktionen kann der Rechenaufwand sehr hoch werden.
  • Potenzielle Überfrachtung mit Schnitten: Zu viele hinzugefügte Schnittebenen können das Problem unnötig kompliziert machen und die Lösung verlangsamen. Dies erfordert eine sorgfältige Verwaltung und Auswahl der Schnittebenen.
  • Schwierigkeit der Schnittgenerierung: Der Prozess der Generierung effektiver Schnittebenen kann komplex sein und eine tiefgehende Kenntnis der Problemstruktur erfordern. Nicht jede Schnittebene führt zu einer signifikanten Verbesserung.
  • Numerische Stabilität: Das Hinzufügen vieler Schnitte kann zu numerischen Problemen führen, insbesondere bei sehr fein aufgelösten Schnitten oder wenn viele sehr kleine Koeffizienten auftreten.
• Kombination mit Branch-and-Bound (Branch-and-Cut):
  • Vorteile der Kombination: Die Kombination der Cutting-Plane-Methode mit dem Branch-and-Bound-Algorithmus, bekannt als Branch-and-Cut, ermöglicht es, Zweige des Suchbaums effizienter abzuschneiden und schneller zu einer optimalen Lösung zu gelangen. Diese Hybrid-Methode nutzt die Schnittebenen, um die Relaxierungslösungen des Branch-and-Bound-Verfahrens zu verbessern, was zu einer schnelleren Konvergenz führt.
  • Effizienzsteigerung: Durch die Platzierung von Schnittebenen in einzelnen Zweigen des Branch-and-Bound-Baums kann die Effizienz der Methode maximiert werden, indem unwichtige Teile des Baums rasch ausgeschlossen werden.
  • Flexibilitätsvorteile: Die Möglichkeit, an verschiedenen Stellen des Branch-and-Bound-Baums Schnitte hinzuzufügen, bietet eine flexible und anpassungsfähige Optimierungsstrategie.
• Effizienz der Methode:
  • Anwendung in der Praxis: In der Praxis wird die Effektivität der Cutting-Plane-Methode maßgeblich durch die Auswahl der Schnittebenen und die Kombination mit anderen Optimierungsmethoden bestimmt. Software-Tools wie Cplex und Gurobi haben hocheffiziente Algorithmen integriert, die diese Methoden kombinieren und optimieren.
  • Problemabhängigkeit: Die Effizienz der Cutting-Plane-Methode hängt stark von der spezifischen Problemstruktur ab. Manche ILPs profitieren mehr von schnittorientierten Methoden, während andere besser mit reinen Branch-and-Bound-Strategien gelöst werden.

Insgesamt bietet die Cutting-Plane-Methode in Kombination mit dem Branch-and-Bound-Verfahren eine leistungsfähige und vielseitige Methode zur Lösung von ILPs. Die Wahl der richtigen Schnittebenen und die effiziente Integration der Methoden ist entscheidend für den Erfolg und die Effizienz dieser Ansätze.