Discrete optimization I - Cheatsheet

Mathematische Modellierung diskreter Probleme

Definition:

Modellierung diskreter Optimierungsprobleme durch mathematische Formulierungen, meist mit Variablen, die ganzzahlige Werte annehmen.

Details:

• Variablen: Integer, binär
• Ziel: Funktion zur Optimierung (Minimierung/Maximierung)
• Nebenbedingungen: Gleichungen/Ungleichungen
• Beispiele: Rucksackproblem, Travelling Salesman Problem
• Zielfunktion: \[ \text{min/max } f(x) \]
• Constraints: \[ g_i(x) \leq b_i, \forall i \]

Der Simplex-Algorithmus und seine Varianten

Definition:

Simplex-Algorithmus zur Lösung von LP-Problemen (linearen Programmierungen). Varianten optimieren für spezielle Bedingungen und Effizienz.

Details:

• Ziel: Finden einer optimalen Lösung in einem konvexen Polyeder definiert durch lineare Ungleichungen
• Iterative Methode: Bewegt sich entlang der Kanten des Polyeders
• Start in einer Basislösung, dann Übergang zu Nachbarbasislösungen
• Bland's Regel vermeidet Zyklen, verbessert Stabilität
• Dual-Simplex: arbeitet mit unzulässigen Lösungen, verbesserter Umgang mit Nebenbedingungen
• Revised Simplex: spart Speicher durch Arbeit mit reduzierten Problemen
• Practical issues: Degeneration, künstliche Basis, Pivot-Auswahl

Dualitätstheorie und deren Anwendungen

Definition:

Analyse von Optimierungsproblemen durch Transformation in Dualprobleme; Dualität liefert Schranken und notwendige Bedingungen für Optimalität.

Details:

• Primal- und Dualprobleme: Jede LP hat ein zugehöriges Dualproblem.
• Schwache Dualität: Für zulässige Lösungen gilt: Kosten des Dualproblems ≤ Kosten des Primärproblems.
• Starke Dualität: Optimalwerte stimmen überein, wenn beide Probleme zulässige Lösungen haben (nur bei LP, nicht allgemein).
• KKT-Bedingungen: Notwendige und hinreichende Bedingungen für Optimalität (bei konvexen Problemen).
• Anwendung: Berechnung von Schranken, Umformulation von Problemen, Sensitivitätsanalyse.

Branch-and-Bound-Methoden

Definition:

Methode zur Lösung von diskreten Optimierungsproblemen, indem der Suchraum systematisch durchsucht wird durch Zerlegen in Teilprobleme (Branching) und Schranken für optimale Werte (Bounding).

Details:

• Erkundungsbaum strukturiert die Problemlösung.
• Verwendet obere und untere Schranken zur Reduktion des Suchraums.
• Verzicht auf bestimmte Zweige, wenn Schranken keine verbesserten Lösungen versprechen.
• Anwendung bei: Ganzzahlige Optimierung, kombinatorische Probleme.
• Ziel: Effizienz durch minimales Durchsuchen.

Cutting-Plane-Verfahren

Definition:

Methode zur Lösung von Ganzzahlproblemen durch sukzessives Hinzufügen von Geraden (Schnitte) zur Eingrenzung des Lösungsraums.

Details:

• Beginnt mit der Lösung des Relaxierungsproblems (ohne Ganzzahligkeitsbeschränkungen).
• Findet Schnittebenen, die den nicht-ganzzahligen Teil des Lösungsraums eliminieren.
• Fügt Schneidebedingungen zur aktuellen Relaxierung hinzu.
• Wiederholt den Prozess, bis eine ganzzahlige Lösung gefunden wird.
• Verwendet oft Gomory-Cuts für lineare Probleme.
• Effektiv für MILP-Probleme.
• Algorithmus kann in LP-Solver integriert werden.

Max-Flow Min-Cut Theorem

Definition:

Der Max-Flow Min-Cut Theorem besagt, dass der maximale Fluss in einem Flussnetzwerk gleich der Kapazität des minimalen Schnitts durch das Netzwerk ist.

Details:

• Maximaler Fluss (\textit{max-flow}): Der größte mögliche Fluss, der von der Quelle (\textit{source}) zum Ziel (\textit{sink}) fließen kann.
• Minimaler Schnitt (\textit{min-cut}): Die kleinste Kapazität der Kantenmenge, deren Entfernung das Netzwerk in zwei disjunkte Mengen trennt, mit der Quelle in einer und dem Ziel in der anderen.
• Formel: \textit{max-flow} = \textit{min-cut}
• Anwendungen: Netzwerkplanung, Transportlogistik, Bildsegmentierung, etc.

Metaheuristiken wie Simulated Annealing und Tabu Search

Definition:

Metaheuristiken sind allgemeine, problemunabhängige Lösungsansätze zur näherungsweisen Lösung schwieriger Optimierungsprobleme.

Details:

• Simulated Annealing: basiert auf dem Abkühlen eines Metalls. Akzeptiert auch schlechtere Lösungen mit einer gewissen Wahrscheinlichkeit, um globale Optima zu finden.
• Formeln:
• Akzeptanzwahrscheinlichkeit: \(P(E,E') = e^{(f(E) - f(E')) / T}\)
• Tabu Search: verwendet eine adaptive Speicherstruktur (Tabuliste), um Rückschritte zu vermeiden und die Lösungssuche zu diversifizieren.
• Kernelemente:
• Tabuliste: Speichert kürzlich besuchte Lösungen, um Zyklen zu vermeiden.
• Aspirationskriterium: Erlaubt Tabuschritte, wenn sie zu einer besseren Lösung führen.

Lineare Relaxation und Cutting Planes bei ganzzahliger Programmierung

Definition:

Lineare Relaxation: Ganzzahlige Variablen als kontinuierliche Variablen behandeln. Cutting Planes: Zusätzliche Ungleichungen einführen, um unzulässige Ganzzahllösungen auszuschließen.

Details:

• Lineare Relaxation: Ursprüngliches Problem ohne Ganzzahlanforderungen lösen.
• Ziel: Näherungslösung und obere Schranke finden.
• Cutting Planes: Iterativ zusätzliche Schnitte einführen, um den Lösungsraum zu verengen.
• Gomory-Cuts: Häufig verwendete Methode zur Generierung von Schnitten.
• Fenchel-Cuts, Knapsack-Cuts: Weitere Techniken für spezielle Problemklassen.