LP-Relaxation

Als LP-Relaxation (abgeleitet von Lineare Programmierung) wird bezeichnet, wenn bei einem Problem der ganzzahligen linearen Optimierung die Forderung der Ganzzahligkeit aufgegeben wird.

So ersetzt man z. B. Nebenbedingungen der Gestalt

${\displaystyle x_{i}\in \{0,1\}}$

des originalen ganzzahligen Optimierungsproblems durch die relaxierten Nebenbedingungen

${\displaystyle 0\leq x_{i}\leq 1.}$

Das Problem („Programm“) lässt sich in der relaxierten Form mit Hilfe der linearen Optimierung lösen. Die so entstandene reelle Lösung erfüllt nur in Ausnahmefällen die Ganzzahligkeitsbedingungen des ursprünglichen Problems, mit ihrer Hilfe können jedoch Schlüsse über die Lösung des ursprünglichen Problems gezogen werden. Die Lösung des relaxierten Problems kann auch als Näherungslösung für einen Algorithmus zur ganzzahligen Optimierung verwendet werden.

Dies ist von Interesse, da durch die LP-Relaxation ein NP-schweres (ganzzahliges) Optimierungsproblem in ein verwandtes (reelles) Problem transferiert wird, welches in polynomialer Zeit gelöst werden kann.

Die Methode wurde von Shmuel Agmon im Jahr 1954 beschrieben.

Von einer Relaxation im Kontext eines Optimierungsproblems (z. B. Maximierung einer Zielfunktion) wird allgemein dann gesprochen, wenn die Menge zulässiger Lösungen vergrößert wird. Hierdurch wird der maximale Zielfunktionswert nicht verkleinert.