LP-relaxatie

In de wiskunde is LP-relaxatie de verandering van een lineaire- programmeringsprobleem met geheeltallige beperkingen door de eis van geheeltalligheid van de variabelen te laten vallen. Het toegelaten gebied kan hierdoor groter worden, waardoor het mogelijk gemakkelijker opgelost kan worden. Er moet dan later wel gecontroleerd worden of de verkregen optimale oplossing aan de oorspronkelijke eisen van geheeltalligheid voldoet, wat waarschijnlijk niet het geval zal zijn. Wel zal de gevonden oplossing gebruikt kunnen worden als een benaderende oplossing voor het oorspronkelijke geheeltallige probleem.

Men vervangt bijvoorbeeld nevenvoorwaarden van de vorm

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

in het oorspronkelijke geheeltallige programmeringsprobleem door de 'gerelaxeerde' beperkingen

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

De methode is beschreven door Shmuel Agmon in 1954.

Literatuur

Shmuel Agmon: The relaxation method for linear inequalities, Canadian Journal of Mathematics, Nr. 6, S. 382–392 (1954).