Optimalitätslücke

Die Optimalitätslücke misst den Abstand zwischen dem Wert der besten gefundenen zulässigen Lösung (obere Schranke UB bei Minimierung) und der besten bisher erzielten dualen Schranke (untere Schranke LB); es bestehen zwei Standarddefinitionen. Absolute Lücke = |UB - LB|. Relative Lücke (die kanonische MILP-Variante) = |UB - LB| / max(ε, |UB|), in einigen Lösern auch |UB - LB| / max(ε, |LB|) — die Wahl des Nenners variiert je nach Anbieter, ε schützt vor Division durch null. Eine Lücke von null zertifiziert den Incumbent als optimal und beendet den Algorithmus; in der Praxis stoppen Löser mit 'fast-optimal'-Flag, sobald die Lücke unter eine vom Nutzer festgelegte Toleranz (oft 0,01-1 %) fällt. Logische Grundlage ist die Dualitätstheorie: in der LP-Welt liefert die schwache Dualität UB ≥ LB für jedes primal-duale zulässige Paar, die starke Dualität wandelt diese Ungleichung in Gleichheit um. Bei MILP erzeugt die LP-Relaxation die LB, Branch-and-Bound aktualisiert die LB knotenweise, primale Heuristiken und die Branching-Exploration aktualisieren die UB. Interpretation: 5 % Lücke bedeutet 'der Lösungswert ist höchstens 5 % schlechter als das Optimum' — eine Verbesserung unterhalb der bekannten LB ist mathematisch unmöglich. Praktische Anwendungen umfassen Risikokommunikation an das Management, Abbruchentscheidungen (Zeit-Qualitäts-Trade-off bei langen Branch-and-Cut-Läufen) und Benchmark-Vergleiche von Heuristiken. Lagrange-Dualitätslücke in der konvexen nichtlinearen Programmierung und Relaxationslücke in der nicht-konvexen Programmierung sind analoge Begriffe. Standardreferenzen: Nemhauser und Wolsey (1988) und Wolsey (1998).