Integer Optimization - Cheatsheet.pdf

Grundlegende Konzepte der ganzzahligen Programmierung

Definition:

Mathematisches Optimierungsproblem, bei dem einige oder alle Variablen ganzzahlig sein müssen.

Details:

• Zielfunktion: Linear oder nicht-linear
• Variablen: Ganzzahlige Werte erforderlich
• Constraints: Gleichungen oder Ungleichungen, die die Zulässigkeit der Lösung definieren
• Branch-and-Bound: Algorithmus zur Lösung
• Relaxation: Umwandlung in ein lineares Programm zur einfachen Lösung

Branch-and-Bound und Branch-and-Cut Verfahren

Definition:

Branch-and-Bound und Branch-and-Cut sind grundlegende Methoden zur Lösung von ganzzahligen Optimierungsproblemen.

Details:

• Branch-and-Bound: Unterteile das Problem rekursiv in kleinere Teilprobleme (Branching).
• Nutze Schranken (Bounds), um Teilprobleme auszuschließen.
• Lösung läuft in einem Baum-Suchverfahren ab.
• Branch-and-Cut: Kombination von Branch-and-Bound mit Cutting Planes.
• Cutting Planes: Hinzufügen von Schnittebenen, die die zulässige Lösungsmenge reduzieren.
• Effiziente Implementierung für große Probleme erforderlich.

Komplexität und Lösungsstrategien

Definition:

Untersucht die Komplexität von Problemen und entwickelt Strategien zur effizienten Lösung ganzzahliger Optimierungsprobleme.

Details:

• Schwierigkeitsklassifizierung: P, NP, NP-vollständig
• Lineare Programmierung (LP) und polyhedrale Methoden
• Branch and Bound
• Cutting-Plane Methode
• Heuristiken und Approximationsalgorithmen
• Komplexitätstheorie: Polynomialzeit, exponentielle Laufzeit
• Problemreduktion und Transformation
• Dualität und Relaxationen: Lagrange-Relaxation, LP-Relaxation
• Implementierungseffizienz und Optimierung

Heuristiken und Metaheuristiken

Definition:

Heuristiken: Lösungsverfahren, die schnelle, aber nicht notwendigerweise optimale Lösungen liefern. Metaheuristiken: Übergeordnete Strategien, die Heuristiken leiten und optimieren.

Details:

• Heuristiken: Schnelle Lösungsfindung, keine Garantie für Optimalität
• Metaheuristiken: Setzen Heuristiken ein, um Suchprozess zu steuern und zu optimieren
• Bekannte Metaheuristiken: Genetische Algorithmen, Simulierte Abkühlung
• Ziel: Näherung optimaler Lösungen für schwierige Optimierungsprobleme

Simplex-Algorithmus und Dualitätstheorie

Definition:

Simplex-Algorithmus: Verfahren zur Lösung linearer Programme durch iteratives Optimieren entlang der Ecken des Polyeders. Dualitätstheorie: Jedes lineare Programm hat ein zugehöriges duales Programm, das Informationen über die Lösung des primären Programms liefert.

Details:

• Simplex-Algorithmus startet an einer Ecklösung und bewegt sich entlang der Kanten zu benachbarten Ecken mit besserem Zielfunktionswert.
• Endet an der optimalen Lösung oder zeigt Unbeschränktheit/Unlösbarkeit.
• Dualität: Für jedes primale LP existiert ein duales LP.
• Schwaches Dualitäts-Theorem: Jede zulässige Lösung des dualen LP ist eine untere Schranke für die Zielfunktion des primären LP.
• Starkes Dualitäts-Theorem: Die optimalen Werte der Zielfunktionen im primären und dualen LP sind gleich.
• Komplementäre Schlupfbedingungen: Optimalitätsbedingungen, die besagen, dass das Produkt der Primal- und Dualvariablen gleich null ist.

Polyedertheorie und lineare Ungleichungssysteme

Definition:

Polyedertheorie befasst sich mit der Untersuchung von Polyedern, die durch lineare Ungleichungssysteme beschrieben werden.

Details:

• Ein Polyeder ist die Menge aller Lösungen eines linearen Ungleichungssystems.
• Allgemeine Form: Ax leq b.
• Stützhyere: Hyperebene, die ein Polyeder nicht schneidet.
• Ecke: Extremalpunkt eines Polyeders.
• Kegelmantel: Polyeder, das von einem Kegel aufgespannt wird.
• Beschränkter Polyeder: Kompaktes Polyeder.

Produktionsplanung und Logistik

Definition:

Produktionsplanung und Logistik befasst sich mit der Optimierung der Produktion und der Verteilung von Gütern unter Berücksichtigung von Kapazitäten, Nachfrage und Kosten.

Details:

• Ziele: Minimierung der Kosten, Maximierung der Effizienz
• Modellierung mit Ganzzahligen Optimierungsproblemen
• Zentrale Begriffe: Maschinenbelegung, Losgrößenplanung, Lieferkettenmanagement
• Typische Modelle: \textit{Job-Shop Scheduling}, \textit{Traveling Salesman Problem} (TSP)
• Verfahren: Lineare Programmierung (LP), Branch and Bound, Schnittebenenverfahren

Optimierung in der Energiesysteme

Definition:

Optimierung von Energiesystemen mittels Integer Optimierung zur Minimierung der Kosten oder Maximierung der Effizienz unter Berücksichtigung von Restriktionen und Kapazitäten.

Details:

• Verwendung von Ganzzahlvariablen zur Modellierung von An- und Ausschaltzuständen (z.B. Kraftwerke).
• Ziel: Kostenminimierung oder Effizienzmaximierung.
• Berücksichtigung von: Erzeugungskapazitäten, Nachfrage, Netzstabilität.
• Häufig verwendete Modelle: Mixed-Integer Linear Programming (MILP), Mixed-Integer Nonlinear Programming (MINLP).
• Formulierung: Entscheidungsvariablen, Zielfunktion, Nebenbedingungen.
• Beispiel: Zielfunktion \( \text{min} \ \text{Kosten} = \sum_{i} c_i \cdot x_i \), wobei \( c_i \) die Kosten und \( x_i \) die Betriebszustände sind.
• Mathematische Darstellung typischer Restriktionen: Leistungsbilanz \( \text{Erzeugung} = \text{Verbrauch} \), Kapazitätsgrenzen \( 0 \le x_i \le \text{Kapazität}_{i} \).