Ganzzahlige lineare Optimierung

Komplexität und Lösungsverfahren

Lagrange-Relaxierung

Hauptartikel: Lagrange-Multiplikator

Die Lagrange-Relaxierung ist ein Verfahren aus der nichtlinearen Optimierung, das auch auf die ganzzahlige Optimierung angewandt werden kann. Die Grundidee besteht darin, „störende“ Ungleichungen wegzulassen, so dass das verbleibende Problem (mit Ganzzahligkeitsbedingungen) leicht lösbar ist, und statt dessen die Verletzung dieser Ungleichungen, gewichtet mit sogenannten Lagrange-Multiplikatoren, in der Zielfunktion zu bestrafen.

Eine Lösung dieses einfacheren Problems wird in den meisten Fällen die in die Zielfunktion relaxierten Bedingungen nicht erfüllen. Um dies zu ändern, werden die Lagrange-Multiplikatoren mit Hilfe eines Subgradientenverfahrens abhängig von der aktuellen (unzulässigen) Lösung so angepasst, dass ein erneutes Lösen mit den neuen Gewichten eine etwas „zulässigere“ Lösung erzeugt, welche die relaxierten Ungleichung weniger stark verletzt. Dieser Prozess wird iterativ wiederholt, bis alle Bedingungen erfüllt sind. Man kann zeigen, dass jede Lösung einer Lagrange-Relaxierung eine duale Schranke für das ursprüngliche IP liefert, und dass dieses Verfahren bei geeigneter Anpassung der Multiplikatoren konvergiert.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Ganzzahlige lineare Optimierung aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung