Approximationsalgorithmen - Cheatsheet

Modelle und Definitionen linearer Programme

Definition:

Lineare Programme sind mathematische Modelle zur Lösung von Optimierungsproblemen, bei denen eine lineare Funktion maximiert oder minimiert wird, unter Nebenbedingungen, die durch lineare Gleichungen und Ungleichungen dargestellt werden.

Details:

• Allgemeine Form: Maximiere/Minimiere: \(c^T x\)
• Unter Nebenbedingungen: \(Ax \le b\), \(x \ge 0\)
• \(x\) ist der Vektor der Entscheidungsvariablen
• \(c\) ist der Vektor der Zielfunktion
• \(A\) ist die Matrix der Nebenbedingungen
• \(b\) ist der Vektor der rechten Reiseite der Nebenbedingungen

Simplex-Algorithmus und seine Anwendungen

Definition:

Algorithmus zur Lösung linearer Optimierungsprobleme.

Details:

• Formuliert durch George Dantzig 1947.
• Arbeitet durch schrittweise Bewegung entlang der Kanten des zulässigen Bereichs zu einer optimalen Ecke.
• Zur Maximierung oder Minimierung einer linearen Zielfunktion unter linearen Nebenbedingungen.
• Komplexität: Im Durchschnitt effizient, aber Worst-Case exponentiell.
• Beliebte Anwendungen: Logistik, Produktionsplanung, Netzwerkflussprobleme.

Branch-and-Bound-Algorithmus

Definition:

Algorithmus zur Lösung von Optimierungsproblemen durch systematisches Durchsuchen des Lösungsraums und Abschneiden von nicht vielversprechenden Teillösungen.

Details:

• Hauptmechanismen: Zerlegen (Branching), Schranken setzen (Bounding), Pruning.
• Exploration eines Suchbaums, wobei jeder Knoten eine Teillösung darstellt.
• Obere und untere Schranken zur Abschätzung der Güte einer Lösung.
• Wenn eine Schranke einer Teillösung schlechter ist als die beste gefundene Lösung, wird dieser Suchpfad verworfen (Pruning).
• Geeignet für Probleme wie das Rucksackproblem, das Traveling Salesman Problem und gemischt-ganzzahlige lineare Programme (MILP).
• Anwendung in exakten Algorithmen und nicht in approximativen Algorithmen.

Cutting-Plane-Methoden

Definition:

Optimierungsverfahren zum Lösen von ganzzahligen linearen Programmen (ILP), indem sukzessive Schnittebenen hinzugefügt werden, um die zulässige Lösungsmenge einzugrenzen.

Details:

• Ziel: Approximierung der optimalen Lösung durch iteratives Hinzufügen von Schnittebenen.
• Schnittpunkte/Aufschneidungen durch Ungleichungen, die keine ganzzahligen Punkte innerhalb des zulässigen Bereichs enthalten.
• Verwendet Cplex, Gurobi oder spezialisierte Tools.
• In Kombination mit Branch-and-Bound: Branch-and-Cut.
• Effizienz stark abhängig von der Wahl der Schnittebenen.
• Beispiele für Schnitte: Gomory-Schnitte, Chvátal-Gomory-Schnitte.

Leistungsanalyse von Approximationsalgorithmen

Definition:

Bewertung der Effizienz und Genauigkeit von Approximationsalgorithmen. Vergleicht die Lösung des Algorithmus mit der optimalen Lösung.

Details:

• Approximation Ratio: Verhältnis der Kosten der erzeugten Lösung zur optimalen Lösung, z.B. \(\frac{C(A)}{C_{opt}}\).
• Konstante Approximationsalgorithmen: Falls das Approximation Ratio eine konstante obere Schranke hat, z.B. 2-Approximation.
• Polynomialzeit: Algorithmen, die in polynomieller Zeit laufen.
• PTAS (Polynomial Time Approximation Scheme): Ein Algorithmus, der für jedes \(\epsilon > 0\) eine \(1 + \epsilon\)-Approximation in polynomieller Zeit liefert.
• APX (Approximation): Klasse von Optimierungsproblemen, für die konstante Approximationsalgorithmen existieren.

Greedy-Strategie: Prinzip und Anwendungsfälle

Definition:

Eine Greedy-Strategie trifft in jedem Schritt die lokal optimale Wahl in der Hoffnung, eine globale Lösung zu finden.

Details:

• Prinzip: Immer den aktuell besten Schritt wählen.
• Nicht immer optimal, aber oft effizient.
• Anwendungsfälle:
• Kürzeste Wege (Dijkstra)
• Minimaler Spannbaum (Prim, Kruskal)
• Aktivitätsauswahl
• Kodierung (Huffman)
• Güte der Lösungen hängt stark von der Problemstruktur ab.

Monte Carlo und Las Vegas Algorithmen

Definition:

Monte Carlo Algorithmen: Zufallsbasierte Algorithmen, liefern Lösungen mit einer gewissen Wahrscheinlichkeit der Korrektheit. Las Vegas Algorithmen: Zufallsbasierte Algorithmen, liefern garantiert korrekte Lösung, aber Laufzeit ist zufallsabhängig.

Details:

• Monte Carlo: Lösung in polynomialer Zeit, aber nur mit Wahrscheinlichkeit korrekt
• Las Vegas: Zeitaufwändig kann zufällig variieren, aber Lösung ist korrekt
• Monte Carlo Beispiel: \textit{Primes-Test} von Zahlen
• Las Vegas Beispiel: \textit{Quicksort mit zufälligem Pivot}
• Monte Carlo hat keine garantierten Laufzeiten, jedoch oft effizienter in der Praxis
• Las Vegas bietet Berechnungen an, die irgendwann enden, aber Dauer nicht vorhersagbar ist

Handel zwischen Genauigkeit und Rechenzeit

Definition:

Abwägung zwischen der Genauigkeit eines Approximationsalgorithmus und der benötigten Rechenzeit.

Details:

• Genauigkeit bemisst sich durch den Approximationsfaktor \ \( \rho \ \), Ratio zwischen Approximationswert und optimalem Wert.
• Rechenzeit ist oft polynomiell abhängig von der Problemgröße \( n \).
• Trade-off notwendig: Erhöhte Genauigkeit führt häufig zu längerer Rechenzeit.
• Bekannte Approximationen: PTAS (polynomial-time approximation scheme) und FPTAS (fully polynomial-time approximation scheme).