Integer Optimization - Exam.pdf

Aufgabe 1)

Betrachte ein ganzzahliges Optimierungsproblem, bei dem die Zielfunktion linear ist und alle Variablen ganzzahlig sein müssen. Das Optimierungsproblem sei wie folgt definiert:

• Zielfunktion: Minimiere z = c₁x₁ + c₂x₂
• Variablen: x₁, x₂ ∈ ℤ
• Constraints: a₁x₁ + a₂x₂ ≥ b

a)

(a) Führe eine Branch-and-Bound-Analyse für das folgende Problem durch:

• zielfunktion: Minimiere z = -x₁ + 2x₂
• Constraints: 2x₁ + 3x₂ ≥ 6 und x₁ ≥ 0, x₂ ≥ 0

Zeichne den Entscheidungsbaum und bestimme die optimale ganzzahlige Lösung.

Lösung:

Branch-and-Bound-Analyse:

Wir haben das folgende ganzzahlige Optimierungsproblem:

• Zielfunktion: Minimiere z = -x₁ + 2x₂
• Constraints: 2x₁ + 3x₂ ≥ 6 und x₁ ≥ 0, x₂ ≥ 0

Schritt-für-Schritt-Lösung:

Schritt 1: Löse zuerst das Relaxed-Problem (ohne ganzzahlige Beschränkungen) durch Lineare Programmierung (LP).

Das LP-Problem lautet:

• Zielfunktion: Minimiere z = -x₁ + 2x₂
• Constraints: 2x₁ + 3x₂ ≥ 6 und x₁ ≥ 0, x₂ ≥ 0

Wir verwenden die Methode der Schnittpunkte, um dieses LP-Problem zu lösen:

1. Setze x₁ = 0, dann 3x₂ = 6 ⟹ x₂ = 2
2. Setze x₂ = 0, dann 2x₁ = 6 ⟹ x₁ = 3

Die möglichen Schnittpunkte der Beschränkung 2x₁ + 3x₂ ≥ 6 sind (0, 2) und (3, 0). Die Zielfunktion z wird bei diesen Punkten wie folgt berechnet:

• Für (0, 2): z = -0 + 2*2 = 4
• Für (3, 0): z = -3 + 2*0 = -3

Die niedrigste Zielfunktion wird bei Punkt (3, 0) erreicht, z = -3.

Schritt 2: Überprüfe, ob (3, 0) eine gültige ganzzahlige Lösung ist:

• Da x₁ = 3 und x₂ = 0 ganzzahlig sind und die Constraint 2x₁ + 3x₂ ≥ 6 erfüllt wird (6 ≥ 6), ist (3, 0) die optimale ganzzahlige Lösung.

Entscheidungsbaum

Da die Lösung bereits in den ersten Schritten gefunden wurde und keine zusätzlichen Branches erforderlich waren, ist der Entscheidungsbaum sehr einfach:

• Starte bei der Relaxed-Lösung (3, 0)
• Überprüfe die Ganzzahligkeit: beide Variablen sind ganzzahlig
• Bestimme die Zielfunktion z für (3, 0): z = -3
• Ende

Optimale Ganzzahlige Lösung

• (x₁, x₂) = (3, 0)
• Minimale Zielfunktion z = -3

b)

(b) Führe die Relaxation des Problems aus Teil (a) durch und löse das resultierende lineare Programm:

• Zielfunktion: Minimiere z = -x₁ + 2x₂
• Constraints: 2x₁ + 3x₂ ≥ 6 und x₁ ≥ 0, x₂ ≥ 0

Berechne die optimalen Werte für x₁ und x₂, wenn die Variablen nicht auf ganzzahlige Werte beschränkt sind. Vergleiche das Ergebnis mit der Lösung der Branch-and-Bound-Analyse aus Teil (a).

Lösung:

Relaxation des Problems und Lösung des resultierenden linearen Programms

Wir haben das folgende lineare Optimierungsproblem ohne die Beschränkung auf ganzzahlige Variablen:

• Zielfunktion: Minimiere z = -x₁ + 2x₂
• Constraints: 2x₁ + 3x₂ ≥ 6 und x₁ ≥ 0, x₂ ≥ 0

Um dieses lineare Programm zu lösen, analysieren wir die möglichen Schnittpunkte und verwenden die Methode der Schnittpunkte:

1. Setze x₁ = 0:a) 2x₁ + 3x₂ ≥ 6 ⟹ 3x₂ ≥ 6 ⟹ x₂ = 2
2. Setze x₂ = 0:a) 2x₁ + 3x₂ ≥ 6 ⟹ 2x₁ ≥ 6 ⟹ x₁ = 3

Wir müssen auch den Schnittpunkt ermitteln, an dem beide Constraints gleich sind.

Setze 2x₁ + 3x₂ = 6:

• Die beiden Constraints sind Linien 2x₁ + 3x₂ = 6 und die Achsenabschnitte sind (3, 0) und (0, 2). Es gibt keinen weiteren Schnittpunkt zwischen den Constraints und den Achsen.

Berechnung der Zielfunktion:

• Für (0, 2): z = -0 + 2*2 = 4
• Für (3, 0): z = -3 + 2*0 = -3

Da wir alle relevanten Punkte untersuchen müssen (da es sich um ein LP handelt), betrachten wir auch Prozesse in der Nähe von gültigen Werten, um sicherzustellen, dass keine bessere Lösung existiert:

• Der Punkt, der uns die optimale Lösung bei z = -3 liefert, ist (3,0). Der Wert entspricht der Berechnung des ganzzahligen Problems bei (3, 0) ebenfalls mit z = -3.

Vergleich mit der Branch-and-Bound-Lösung

• In beiden Fällen, sowohl in der Relaxation als auch im Branch-and-Bound-Verfahren, liegt die optimale Lösung bei (x₁ = 3, x₂ = 0).
• Der optimale Wert der Zielfunktion beträgt in beiden Verfahren z = -3.

Aufgabe 2)

Du hast ein ganzzahliges Optimierungsproblem gegeben. Betrachte das folgende Problem: **Maximiere**: `z = 5x_1 + 3x_2` **unter den Bedingungen**: `x_1 + 2x_2 \leq 10` `3x_1 + x_2 \leq 12` `x_1, x_2 \in \mathbb{Z}^+` Verwende das Branch-and-Bound und das Branch-and-Cut Verfahren, um dieses Problem zu lösen.

c)

Vergleiche die Effizienz von Branch-and-Bound und Branch-and-Cut für dieses spezifische Problem. Diskutiere die Vor- und Nachteile beider Methoden und gib an, unter welchen Umständen eine Methode der anderen vorzuziehen wäre.

Lösung:

Vergleich der Effizienz von Branch-and-Bound und Branch-and-Cut Verfahren für das gegebene Problem

Um die Effizienz von Branch-and-Bound und Branch-and-Cut für das gegebene Optimierungsproblem zu vergleichen, betrachten wir die Stärken und Schwächen beider Methoden und in welchen Situationen sie effektiv angewendet werden können.

1. Branch-and-Bound Verfahren

Branch-and-Bound arbeitet durch sukzessive Aufteilung des Lösungsraums (Branching) und Berechnung der Grenzen (Bounding) für jede Teilmenge.

Vorteile:

• Einfach zu implementieren und konzeptionell zu verstehen.
• Generische Methode, die für viele Arten von Optimierungsproblemen anwendbar ist.
• Garantiert die Erreichung der optimalen Lösung, wenn genügend Rechenzeit zur Verfügung steht.

Nachteile:

• Kann sehr zeitaufwändig und speicherintensiv sein, insbesondere für große oder komplexe Probleme.
• Die Effizienz hängt stark von der Qualität der Schranken und der Auswahl der Teilprobleme ab.

Branch-and-Bound Effizienz für das gegebene Problem:

Das gegebene Problem hat zwei Variablen und zwei Ungleichungsbeschränkungen. Branch-and-Bound kann effizient handeln, indem es den kleinen Lösungsraum schnell durchgeht. In diesem Fall, durch einfache Berechnung und kleine Anzahl an Zweigen, erreicht das Branch-and-Bound Verfahren die optimale Lösung relativ schnell.

2. Branch-and-Cut Verfahren

Branch-and-Cut kombiniert Branch-and-Bound mit dem Einfügen von Cutting Planes, um den Lösungsraum zu beschränken und unnötige Bereiche auszuschließen.

Vorteile:

• Kann den Lösungsraum schneller eingrenzen, indem nicht-ganzzahlige Lösungen ausgeschlossen werden.
• Effizienter für größere oder komplexere Probleme, da Cutting Planes die Suchmenge signifikant reduzieren können.
• Reduziert die Anzahl der erforderlichen Branches, was zu schnelleren Lösungen führen kann.

Nachteile:

• Komplexer in der Implementierung im Vergleich zu Branch-and-Bound.
• Erfordert zusätzliche Zeit für die Identifikation und Berechnung von Cutting Planes.
• Anwendung und Wirksamkeit hängen stark von der Problembeschaffenheit und den generierten Cutting Planes ab.

Branch-and-Cut Effizienz für das gegebene Problem:

Obwohl das gegebene Problem relativ klein ist, kann Branch-and-Cut dennoch nützlich sein, insbesondere wenn die Relaxierung viele nicht-ganzzahlige Lösungen zulässt. Durch das Hinzufügen von Cutting Planes könnten die nicht-zulässigen Lösungen schnell ausgeschlossen werden, was den Algorithmus effizienter macht. Besonders bei komplexeren, größeren Problemen würde Branch-and-Cut seine Stärken zeigen.

Empfehlung: Wann welche Methode bevorzugt wird

Branch-and-Bound:

• Für kleinere Probleme mit wenigen Variablen und Nebenbedingungen.
• Wenn Implementierungsaufwand gering gehalten werden soll.
• In Situationen, wo schnelle Prototypenbildung erforderlich ist.

Branch-and-Cut:

• Für größere und komplexere Probleme mit vielen Variablen und Nebenbedingungen.
• Wenn die Relaxierung viele nicht-ganzzahlige Lösungen zulässt, die effizient ausgeschlossen werden müssen.
• In Situationen, wo die höchste Effizienz und Verkürzung der Rechenzeit entscheidend sind.

Für das gegebene Problem kann Branch-and-Bound aufgrund der kleinen Größe und der einfachen Struktur effizient genug sein. Für komplexere Probleme oder für Anwendungen, die höhere Effizienz erfordern, ist Branch-and-Cut die bevorzugte Methode.

Aufgabe 3)

Ein Unternehmen möchte seine Produktionsprozesse optimieren. Die Produktionslinie stellt drei Produkte her, genannt A, B und C. Die Herstellung jedes Produktes benötigt eine bestimmte Anzahl an Stunden für drei verschiedene Maschinen (M1, M2 und M3). Die Produktionszeiten sind in der Tabelle unten angegeben. Zudem hat jede Maschine pro Tag nur eine begrenzte Anzahl an verfügbaren Stunden. Ziel des Unternehmens ist es, den Gewinn zu maximieren. Der Gewinn pro Produkt beträgt für A: 40 Euro, für B: 35 Euro und für C: 20 Euro. Die täglichen verfügbaren Stunden für die Maschinen betragen: M1: 40 Stunden, M2: 35 Stunden und M3: 25 Stunden. Produktionszeiten (in Stunden) pro Gerät:

• Produkt A: M1: 2, M2: 1, M3: 2
• Produkt B: M1: 3, M2: 2, M3: 1
• Produkt C: M1: 1, M2: 2, M3: 2
• Verfügbare machinenstunden: M1: 40, M2: 35, M3: 25
• Produkte Gewinn: A: 40 Euro, B: 35 Euro, C: 20 Euro

c)

Erkläre, wie das Branch-and-Bound-Verfahren verwendet werden kann, um eine ganzzahlige Lösung für dieses Optimierungsproblem zu finden. Was sind die Vorteile und Nachteile dieser Methode verglichen mit der Anwendung der Simplex-Methode und warum ist es wichtig, ganzzahlige Lösungen zu finden?

Lösung:

Das Branch-and-Bound-Verfahren ist eine gängige Methode zur Lösung von ganzzahligen linearen Optimierungsproblemen (Integer Linear Programming, ILP). Hier ist, wie es angewendet werden kann, um eine ganzzahlige Lösung für das Optimierungsproblem zu finden:

1. Grundidee des Branch-and-Bound-Verfahrens:

• Das Branch-and-Bound-Verfahren wird verwendet, um Lösungen zu finden, wenn die Variablen in einem linearen Programmganzzahlig sein müssen.
• Es basiert auf einer systematischen Erkundung aller möglichen Lösungen durch Branching (Verzweigen) und Bounding (Begrenzung).

2. Schritte des Branch-and-Bound-Verfahrens:

• Zuerst wird das Problem ohne Ganzzahlanforderungen (Relaxierung) mit der Simplex-Methode gelöst. Dies liefert eine Schranke für die optimale Lösung.
• Wenn die Lösung ganzzahlig ist, ist sie optimal. Wenn nicht, wird das Problem in zwei Teilprobleme aufgeteilt, indem eine der nicht ganzzahligen Variablen in die nächstniedrigere und nächsthöhere ganze Zahl gerundet wird.
• Der Prozess wird rekursiv fortgesetzt. Jedes Teilproblem wird erneut relaxiert und gelöst. Wenn eine ganzzahlige Lösung gefunden oder eine Schranke erreicht wird, wird der Ast abgeschlossen (gepruned).
• Dieser Prozess wird fortgesetzt, bis alle möglichen Lösungen erkundet wurden oder keine besseren Lösungen mehr gefunden werden können.

3. Anwendung auf das gegebene Problem:

• Abschließend, wenn wir die Variable x_A, die nicht ganzzahlig ist, erhalten, würden wir zwei Teilprobleme erstellen, eines mit x_A <= Runde(x_A) und eines mit x_A >= Decke(x_A).
• Wir fahren mit jeder Verzweigung fort, bis wir eine ganzzahlige Lösung erhalten oder feststellen, dass keine bessere Lösung existiert.

4. Vorteile und Nachteile des Branch-and-Bound-Verfahrens:

Vorteile:
• Kann optimale ganzzahlige Lösungen für komplexe Probleme finden.
• bietet Flexibilität bei der Lösung von Problemen mit zusätzlichen ganzzahligen Restriktionen.
Nachteile:
• Kann sehr rechenintensiv und zeitaufwändig sein, insbesondere bei großen Problemen.
• Erfordert erheblichen Speicherplatz und Rechenressourcen.

5. Vergleich mit der Simplex-Methode:

• Die Simplex-Methode ist effizienter und schneller für lineare Programme ohne Ganzzahlanforderungen.
• Die Simplex-Methode kann keine ganzzahligen Lösungen garantieren, es sei denn, das Problem ist zufällig ganzzahlig in der optimalen Relaxierung.

6. Bedeutung ganzzahliger Lösungen:

• In vielen realen Anwendungen müssen die Entscheidungen ganzzahlig sein (z.B. Anzahl der produzierten Einheiten kann nicht gebrochen sein).
• Ganzzahlige Lösungen sind oft realistischer und anwendbarer in praktischen Szenarien.

Zusammenfassend ist das Branch-and-Bound-Verfahren eine leistungsfähige Methode zur Lösung ganzzahliger Optimierungsprobleme. Es ist wichtig für Szenarien, in denen Variablen nur ganze Werte annehmen können. Trotz seiner höheren Rechenkomplexität bietet es eine systematische Methode zur Identifizierung optimaler Lösungen, die realen Anforderungen entsprechen.

Aufgabe 4)

Heuristiken und Metaheuristiken sind Ansätze zur Lösung von schwierigen Optimierungsproblemen, bei denen es auf Geschwindigkeit und Qualität der gefundenden Lösungen ankommt. Heuristiken dienen dabei der schnellen Lösungsfindung ohne zwingende Garantie für optimale Ergebnisse, während Metaheuristiken Heuristiken einsetzen, um den Suchprozess systematisch zu steuern und zu verbessern. Zu den bekannten Metaheuristiken gehören Genetische Algorithmen und Simulierte Abkühlung. Ziel ist es, möglichst nahe an optimale Lösungen heranzukommen, was in zahlreichen realen Problemstellungen, wie z.B. der Transportlogistik oder Produktionsplanung, unverzichtbar ist.

a)

Sei gegeben ein Reiseproblem für einen Handelsreisenden (Travelling Salesman Problem, TSP), bei dem eine optimal kurze Rundreise durch eine vorgegebene Anzahl von Städten gesucht wird.

• (a) Erläutere kurz, weshalb Heuristiken zur Lösung des TSP oft bevorzugt werden und nenne zwei typische Heuristiken dafür.
• (b) Beschreibe die Simulierte Abkühlung (Simulated Annealing) als eine Metaheuristik, und erkläre, wie sie verwendet werden kann, um das TSP zu lösen. Gehe dabei auf die wesentlichen Schritte des Algorithmus ein.
• (c) Implementiere in Python eine einfache Version der Simulierten Abkühlung zur Lösung des TSP. Verwende eine zufällige Anfangslösung und definiere eine geeignete Nachbarschaftsstruktur. Kommentiere den Code ausführlich.

Lösung:

Heuristiken und Metaheuristiken sind Ansätze zur Lösung von schwierigen Optimierungsproblemen, bei denen es auf Geschwindigkeit und Qualität der gefundenen Lösungen ankommt. Heuristiken dienen der schnellen Lösungsfindung ohne zwingende Garantie für optimale Ergebnisse, während Metaheuristiken Heuristiken einsetzen, um den Suchprozess systematisch zu steuern und zu verbessern. Zu den bekannten Metaheuristiken gehören Genetische Algorithmen und Simulierte Abkühlung. Ziel ist es, möglichst nahe an optimale Lösungen heranzukommen, was in zahlreichen realen Problemstellungen, wie z.B. der Transportlogistik oder Produktionsplanung, unverzichtbar ist.

• (a) Erläutere kurz, weshalb Heuristiken zur Lösung des TSP (Travelling Salesman Problem) oft bevorzugt werden, und nenne zwei typische Heuristiken dafür.

Antwort: Heuristiken werden zur Lösung des TSP oft bevorzugt, weil sie in der Lage sind, in akzeptabler Zeit gute (wenn auch nicht immer optimale) Lösungen zu liefern. Dies ist besonders wichtig, denn das TSP ist ein NP-schweres Problem, dessen exakte Lösung insbesondere bei einer großen Anzahl von Städten sehr viel Rechenzeit und -ressourcen erfordern kann. Durch die Anwendung von Heuristiken kann der Suchraum effektiv und effizient durchsucht werden.

• Zwei typische Heuristiken für das TSP sind:
• Nearest Neighbor Heuristic: Diese Heuristik startet bei einer zufälligen Stadt und wählt immer die nächstgelegene unbesuchte Stadt als nächsten Schritt.
• Minimum Spanning Tree (MST) Heuristic: Diese Heuristik nutzt den MST-Algorithmus, um eine Annäherung an die Lösung zu finden, indem ein minimaler Baum erzeugt wird und dieser entsprechend modifiziert wird, um einen gültigen TSP-Pfad zu erzeugen.

• (b) Beschreibe die Simulierte Abkühlung (Simulated Annealing) als eine Metaheuristik, und erkläre, wie sie verwendet werden kann, um das TSP zu lösen. Gehe dabei auf die wesentlichen Schritte des Algorithmus ein.

Antwort: Simulierte Abkühlung (Simulated Annealing, SA) ist eine Metaheuristik, die von den Prinzipien des Abkühlungsprozesses in der Metallurgie inspiriert ist. Das Ziel ist es, eine optimale oder nahe optimale Lösung durch schrittweise Verfeinerung einer anfänglichen Lösung zu finden, wobei gelegentliche Verschlechterungen zugelassen werden, um lokale Minima zu vermeiden. Die wesentlichen Schritte des Algorithmus sind:

• Anfangslösung: Erzeuge eine zufällige Startlösung.
• Initialtemperatur: Setze eine anfängliche Temperatur fest.
• Nachbarschaftsstruktur: Definiere, wie Lösungen in der Nähe der aktuellen Lösung generiert werden.
• Akzeptanzkriterium: Wenn eine neue Lösung besser ist, wird diese immer akzeptiert. Wenn sie schlechter ist, wird sie mit einer gewissen Wahrscheinlichkeit abhängig von der Temperatur akzeptiert.
• Temperatursenkung: Die Temperatur wird nach jedem Schritt gesenkt, typischerweise nach einem linearen oder geometrischen Schema.
• Abbruchkriterium: Der Algorithmus endet, wenn die Temperatur auf ein Minimum gesunken ist oder nach einer festen Anzahl von Iterationen.

Für das TSP bedeutet dies konkret, dass eine anfängliche Rundreise zufällig erzeugt wird, und in jedem Schritt zwei Städte getauscht werden, um eine neue mögliche Rundreise zu erzeugen. Diese neue Rundreise wird dann gemäß dem Akzeptanzkriterium bewertet und entweder angenommen oder verworfen.

• (c) Implementiere in Python eine einfache Version der Simulierten Abkühlung zur Lösung des TSP. Verwende eine zufällige Anfangslösung und definiere eine geeignete Nachbarschaftsstruktur. Kommentiere den Code ausführlich.

Antwort:

import random  # Für zufällige Initialisierungen und Nachbarlösungen erforderlich import math  # Für mathematische Berechnungen der Akzeptanzwahrscheinlichkeit erforderlich  # Beispielkoordinaten der Städte cities = [     (0, 0),     (1, 3),     (4, 3),     (6, 1), ]  # Funktion zur Berechnung der euklidischen Distanz def distance(city1, city2):     return math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)  # Funktion zur Berechnung der Gesamtlänge der Rundreise def total_distance(tour):     return sum(distance(tour[i], tour[i + 1]) for i in range(len(tour) - 1)) + distance(tour[-1], tour[0])  # Simulated Annealing Algorithmus def simulated_annealing(cities, initial_temp, cooling_rate, stopping_temp):     # Zufällige Initialisierung der Rundreise     current_solution = cities[:]     random.shuffle(current_solution)     best_solution = current_solution[:]     best_cost = total_distance(best_solution)     current_temp = initial_temp      while current_temp > stopping_temp:         # Erzeuge eine Nachbarlösung durch den Tausch von zwei zufälligen Städten         new_solution = current_solution[:]         i, j = random.sample(range(len(cities)), 2)         new_solution[i], new_solution[j] = new_solution[j], new_solution[i]          current_cost = total_distance(current_solution)         new_cost = total_distance(new_solution)          # Akzeptanzwahrscheinlichkeit berechnen         if new_cost < current_cost or random.random() < math.exp((current_cost - new_cost) / current_temp):             current_solution = new_solution  # Update aktuelle Lösung             if new_cost < best_cost:  # Update beste Lösung falls nötig                 best_solution = new_solution                 best_cost = new_cost          # Temperatur senken         current_temp *= cooling_rate # Lineare Temperaturabsenkung      return best_solution, best_cost  # Parameter für den Simulated Annealing Algorithmus initial_temp = 10000 cooling_rate = 0.995 stopping_temp = 1  # Ausführen des Algorithmus best_tour, best_tour_cost = simulated_annealing(cities, initial_temp, cooling_rate, stopping_temp) print('Beste gefundene Rundreise:', best_tour) print('Kosten der besten Rundreise:', best_tour_cost)

In diesem Python-Code wird eine einfache Version des Simulated Annealing Algorithmus implementiert:

• cities: Eine Liste von Koordinaten der Städte.
• initial_temp: Die anfängliche Temperatur.
• cooling_rate: Die Rate, mit der die Temperatur bei jedem Iterationsschritt gesenkt wird.
• stopping_temp: Die Temperatur, bei der der Algorithmus stoppt.

Der Algorithmus beginnt mit einer zufälligen Rundreise (Lösung) und sucht durch zufällige Tausche von Städten nach besseren Lösungen. Bei jeder Iteration wird die neue Lösung akzeptiert, wenn sie besser ist, oder mit einer gewissen Wahrscheinlichkeit, wenn sie schlechter ist. Dies hilft dem Algorithmus, lokale Minima zu vermeiden, um schließlich eine gute Annäherung an die optimale Lösung zu finden. Bei jedem Schritt wird die Temperatur gesenkt, bis sie eine festgelegte Untergrenze erreicht.