Numerical Aspects of Linear and Integer Programming - Cheatsheet

Grundlagen der linearen Programmierung

Definition:

Grundlegende Konzepte und Methoden zur Lösung von Optimierungsproblemen, bei denen eine lineare Zielfunktion unter linearen Nebenbedingungen optimiert wird.

Details:

• Zielfunktion: \[ c^T x \rightarrow \text{max} \text{ oder } \text{min} \]
• Nebenbedingungen: \[ A x \text{ (<=, =, >=) } b \]
• Machbarkeitsbereich: Lösungsmenge der Nebenbedingungen
• Optimallösung: Punkt im Machbarkeitsbereich, der die Zielfunktion optimiert
• Simplex-Algorithmus: Iterative Methode zur Bestimmung der Optimallösung
• Dualitätstheorie: Verbindung zwischen primärem und dualem Problem

Durchführung und Pivotschritte des Simplex-Algorithmus

Definition:

Durchführung der Pivotoperationen im Simplex-Algorithmus zur schrittweisen Optimierung einer Zielfunktion.

Details:

• Start mit einer zulässigen Basislösung.
• Bestimme die Pivotspalte: Wähle die Variable mit dem höchsten positiven Zielfunktionskoeffizienten.
• Bestimme die Pivotzeile: Wähle diejenige mit dem kleinsten positiven Verhältnis des rechten Randwerts zum Pivotelement.
• Durchführung der Pivotoperation: Aktualisiere die Basisvariablen und den Simplex-Tableau.
• Wiederhole, bis keine positiven Zielfunktionskoeffizienten mehr vorhanden sind.

Branch-and-Bound-Verfahren: Upper und Lower Bounds

Definition:

Verfahren zur Lösung von ganzzahligen und gemischt-ganzzahligen Optimierungsproblemen durch systematisches Durchsuchen und Abschneiden (Bounding) von Teillösungen.

Details:

• Upper Bound (OB): Schlechtestes akzeptables Ergebnis. Wird anfangs durch eine heuristische Lösung oder ein Relaxationsverfahren gebildet.
• Lower Bound (UB): Bestmögliches Ergebnis innerhalb eines Teillösungsraums. Definiert durch das Lösen eines Relaxationsproblems.
• Branching: Aufteilung des Problems in kleinere Teilprobleme durch Festlegung von Variablenwerten.
• Kriterium: Abbruch eines Suchzweigs, wenn LB \(\geq\) OB (keine verbesserte Lösung möglich).
• Zielfunktion bleibt zwischen LB und OB, um den Lösungsraum zu reduzieren und die Berechnungseffizienz zu erhöhen.

Primal-Duale Paarung und starke Dualität

Definition:

primal-duale Paarung und starke Dualität in der linearen Optimierung. Wenn die Optimallösungen des Primals und des Duals übereinstimmen, liegt starke Dualität vor.

Details:

• Primales Problem: \[ \text{min } c^T x \ \text{s.t. } Ax \text{≥} b, \ x \text{≥} 0 \]
• Duales Problem: \[ \text{max } b^Ty \ \text{s.t. } A^T y \text{≤} c, \ y \text{≥} 0 \]
• Starke Dualität: \[ \text{Existieren Optimallösungen } x^* \text{ und } y^*, \text{dann gilt } c^T x^* = b^T y^* \]

Formulierung und Lösbarkeit ganzzahliger Modelle

Definition:

Ganzzahlige Modelle verwenden ganzzahlige Variablen in Optimierungsproblemen.

Details:

• Formulierung: Variablen nur ganzzahlig (\texttt{integer}), z.B. \texttt{x \in \mathbb{Z}}.
• Kennzeichnende Gleichungen und Ungleichungen, die die Lösungsmenge beschreiben.
• Lösbarkeit: Häufig NP-schwer; praktische Ansätze wie Branch-and-Bound, Branch-and-Cut.
• Modellierungsstrategien: Einschränkungen hinzufügen, z.B. über Binärvariablen (\texttt{0} oder \texttt{1})
• Lösung in Praxis oft Heuristiken oder Approximationsalgorithmen.
• Werkzeuge: Gurobi, CPLEX, SCIP.

Schnittebenen und Gomory-Cuts

Definition:

Schnittebenen und Gomory-Cuts sind Methoden zur Lösung gemischt-ganzzahliger lineare Programme, die darauf abzielen, die Menge der zulässigen Lösungen einzugrenzen.

Details:

• Schnittebenen: Zusätzliche Ungleichungen, die fraktionale Lösungen ausschließen, aber zulässige ganzzahlige Lösungen erhalten.
• Gomory-Cuts: Erzeugen Schnittebenen, indem sie aus der optimalen Simplex-Tabelle gebrochenen Teile abschneiden.
• Algorithmus:
  • LP lösen, fraktionale Variable identifizieren
  • Gomory-Cut generieren, zur LP hinzufügen
  • LP erneut lösen, wiederholen bis ganzzahlige Lösung

Greedy-Algorithmen und Approximationsgarantien

Definition:

Greedy-Algorithmen: Algorithmen, die in jedem Schritt die augenblicklich beste Wahl treffen. Approximationsgarantien: Maß für die Qualität einer Näherungslösung im Vergleich zur optimalen Lösung.

Details:

• Greedy-Algorithmen wählen lokal optimale Lösungen in der Hoffnung, eine global optimale Lösung zu finden.
• Beispiele: Kruskal-Algorithmus, Dijkstra-Algorithmus.
• Approximationsfaktor: Verhältnis von Näherungslösung zur optimalen Lösung, oft als \( \alpha \leq \frac{L_A(I)}{L_{OPT}(I)} \) gegeben.
• Verwendung bei Problemen, wo exakte Lösungen schwer zu berechnen sind (z.B. NP-schwere Probleme).

Vergleich und Anwendung bei NP-schweren Problemen

Definition:

Details:

• NP-schwere Probleme: Probleme, die zumindest so schwer sind wie die schwierigsten Probleme in NP.
• Vergleich: Für die Lösung und Analyse von NP-schweren Problemen werden Techniken wie Backtracking, Branch-and-Bound, und heuristische Algorithmen verwendet. Diese Techniken werden oft basierend auf ihrer Effizienz und Anwendung verglichen.
• Anwendung: Einsatz in Bereichen wie Logistik (z.B. Routenplanung), Finanzwesen (z.B. Portfolio-Optimierung), und Informatik (z.B. Graphenprobleme).
• Approximation: Viele NP-schwere Probleme werden durch Approximation gelöst, da exakte Lösungen oft zu zeitaufwendig sind.
• Komplexität: Wichtige Komplexitätsklassen wie NP, NP-vollständig und NP-schwer werden bei der Analyse dieser Probleme verwendet.