Lagrange-Relaxation

Die Lagrange-Relaxation ist ein klassisches Dekompositionsverfahren, das ein Optimierungsproblem mit harten strukturellen Restriktionen auf ein leichteres Teilproblem reduziert, indem die komplizierenden Restriktionen über Lagrange-Multiplikatoren dualisiert werden, die deren Verletzung in der Zielfunktion bestrafen. Die systematische OR-Nutzung begann mit der 1-Baum-Relaxation von Held und Karp (1970, 1971) für das Travelling Salesman Problem, wurde von Geoffrion (1974) im allgemeinen MIP-Rahmen verankert und durch den Handbookbeitrag von Fisher (1981) für Praktiker popularisiert. Im Problem min c·x : A₁x = b₁, A₂x = b₂, x ∈ X dualisieren Multiplikatoren λ die harten A₁x = b₁: L(λ) = min c·x + λ(b₁ - A₁x) : A₂x = b₂, x ∈ X — typischerweise zerfällt dies in Rucksack-, Zuordnungs- oder Kürzeste-Wege-Strukturen mit Polynomialzeit-Lösung. Das Lagrange-Dual max_λ L(λ) liefert eine Lagrange-Schranke, die nie schlechter als die LP-Schranke ist und deren Schwach-Dualitäts-Lücke durch die Ganzzahligkeitslücke des Problems beschränkt ist. Zur Lösung des Duals werden Subgradientenverfahren (Held, Wolfe und Crowder 1974), Bundle-Methoden (Lemaréchal 1975) oder der Volumen-Algorithmus (Barahona und Anbil 2000) eingesetzt. Lagrange-Relaxation wird für primale Schrankenerzeugung und Schrankenverdichtung im Branch and Bound bei GAP, Set Covering, MCNF, kapazitiertem Facility Location und Scheduling genutzt. Wolsey (1998) Kapitel 10 ist die Standardreferenz.