Discrete optimization II - Cheatsheet

Simplex-Algorithmus

Definition:

Simplex-Algorithmus: Verfahren zur Lösung linearer Optimierungsprobleme.

Details:

• Startet in einer Ecke des zulässigen Bereichs, bewegt sich entlang der Kanten
• Ziel ist Minimierung oder Maximierung einer linearen Zielfunktion
• Benutzt Pivot-Operationen zur Verbesserung der Zielfunktion in jedem Schritt
• Erzeugt eine Folge von Basislösungen: Jede Lösung entspricht einem Eckpunkt
• Terminiert, wenn keine weitere Verbesserung möglich
• Mathematische Formulierung: Maximiere \( c^T x \) unter den Nebenbedingungen \( Ax \leq b \) und \( x \geq 0 \)

Dualitätstheorie

Definition:

Beziehung zwischen einem Optimierungsproblem (Primärproblem) und einem daraus abgeleiteten Problem (Dualproblem). Dualitätstheorie hilft zur Analyse und Lösung des ursprünglichen Problems.

Details:

• Jedes lineare Programm (LP) hat ein zugehöriges Dualproblem.
• Primal LP: \[\min~c^T x \quad\text{s.t.}\quad Ax \geq b, x \geq 0\]
• Dual LP: \[\max~b^T y \quad\text{s.t.}\quad A^T y \leq c, y \geq 0\]
• Lösungen des Dualproblems liefern Schranken für das Primärproblem.
• Schwache Dualität: \[c^T x \ge b^T y\]
• Starke Dualität: Optimallösungen von Primal und Dual haben denselben Zielfunktionswert.

Branch-and-Bound Verfahren

Definition:

Ein Verfahren zur Lösung von kombinatorischen Optimierungsproblemen durch systematisches Durchsuchen des Lösungsraums. Es vermindert die Menge der zu durchsuchenden Lösungen durch Berechnung von Schranken.

Details:

• Grundidee: Aufteilung des Problems in Teilprobleme (Branching) und Berechnung von Schranken (Bounding), um Teile des Lösungsraums auszuschließen.
• Bounding: Berechnung einer oberen und/oder unteren Schranke für die Kosten der Lösungen in einem Teilraum.
• Branching: Aufteilung des Problems in mehrere Teilprobleme durch Entscheidungsvariablen.
• Verwendung von Heuristiken zur Verbesserung der Effizienz.
• Kann angewendet werden auf Probleme wie das Rucksackproblem, das Traveling Salesman Problem und die Ganzzahlige Lineare Programmierung.

Cutting-Plane Verfahren

Definition:

Verfahren zur Lösung von Ganzzahloptimierungsproblemen durch Hinzufügen von Ungleichungen (Schnittebenen) zu einem LP-Relaxationsproblem.

Details:

• Ausgangspunkt: LP-Relaxation des Ganzzahlproblems.
• Schnitt: Eine Ungleichung, die lösungsausschließende Teile des LP-Polyeders wegschneidet, aber alle ganzzahligen Punkte behält.
• Iterativer Prozess: wiederholtes Lösen des veränderten LP-Problems und Hinzufügen neuer Schnittebenen.
• Beispiel für Schnitte: Gomory-Schnitte.
• Ziel: Komplettes Ausschließen von nicht-ganzzahligen Lösungen durch Schnittebenen.
• Algorithmus endet, wenn eine ganzzahlige Lösung gefunden ist oder keine weiteren brauchbaren Schnitte existieren.

Ford-Fulkerson Algorithmus

Definition:

Ford-Fulkerson Algorithmus zur Bestimmung des maximalen Flusses in einem Flussnetz.

Details:

• Verwendet Tiefensuche (DFS) oder Breitensuche (BFS)
• Startet mit einem Anfangsfluss von 0: \( f(u, v) = 0 \)
• Solange es einen augmentierenden Pfad gibt, erhöhe den Fluss
• Für jeden Knoten u und v: \( c_f(u, v) = c(u, v) - f(u, v) \) mit Restkapazität \( c_f \)
• Korrigiere Flüsse entlang des augmentierenden Pfads
• Maximaler Fluss erreicht, wenn kein augmentierender Pfad existiert
• Kapazitätsbeschränkungen: \( f(u, v) \leq \ c(u, v) \)

Min-Cut Max-Flow Theorem

Definition:

Min-Cut Max-Flow Satz: Maximale Fluss in einem Netzwerk = minimale Kapazität eines Schnittes.

Details:

• Flussnetzwerk: Graph G(V, E) mit Quelle s und Senke t
• Flussfunktion (f): f(u,v) gibt Fluss von u nach v an
• Kapazität (c): c(u,v) maximale Flussmenge von u nach v
• Max-Fluss: Maximiere \sum_{(s,v) \in E} f(s,v)
• Min-Cut: Trenne V in V_s und V_t, so dass s \in V_s und t \in V_t und minimiere \sum_{(u,v) \in E} c(u,v)
• Satz: Maximaler Fluss = Kapazität des minimalen Schnitts

Genetische Algorithmen

Definition:

Evolutionäre Optimierungsverfahren, die natürliche Selektion und genetische Mechanismen simulieren.

Details:

• Bevölkerung (Population) aus potenziellen Lösungen
• Fitnessfunktion: Bewertet Lösungsqualität
• Selektion: Auswahl der besten Individuen
• Kreuzung (Crossover): Kombiniert Merkmale von Elternlösungen
• Mutation: Zufällige Änderungen zur Diversifikation
• Ablauf: Initialisierung, Iteration über Generationen mit Selektion, Kreuzung, Mutation, Bewertung, Eventuelles Abbrechen

NP-vollständige Probleme

Definition:

NP-vollständige Probleme sind eine Klasse von Problemen in der Komplexitätstheorie, die sowohl in NP liegen als auch NP-hart sind.

Details:

• Problem ist in NP: Lösung kann in polynomieller Zeit verifiziert werden.
• NP-hart: Jedes Problem in NP kann in polynomieller Zeit auf dieses Problem reduziert werden.
• Beispiele: SAT, 3-SAT, CLIQUE, HAMILTON-KREIS
• Keine bekannte Methode, um NP-vollständige Probleme in polynomieller Zeit zu lösen.
• Falls ein NP-vollständiges Problem in polynomieller Zeit gelöst wird (P = NP), können alle Probleme in NP in polynomieller Zeit gelöst werden.