Lagrangian relaxation

Lagrangian relaxation is a relaxation technique which works by moving hard constraints into the objective so as to exact a penalty on the objective if they are not satisfied.

Mathematical description

Given an LP problem $x\in \mathbb {R} ^{n}$ and $A\in \mathbb {R} ^{m,n}$ on the following form:

max		$c^{T}x$
s.t.
		$Ax\leq b$

If we split the constraints in $A$ such that $A_{1}\in \mathbb {R} ^{m_{1},n}$, $A_{2}\in \mathbb {R} ^{m_{2},n}$ and $m_{1}+m_{2}=m$ we may write the system:

max		$c^{T}x$
s.t.
(1)		$A_{1}x\leq b_{1}$
(2)		$A_{2}x\leq b_{2}$

We may introduce the constraint (2) into the objective:

max		$c^{T}x+\lambda ^{T}(b_{2}-A_{2}x)$
s.t.
(1)		$A_{1}x\leq b_{1}$

If we let $\lambda =(\lambda _{1},\ldots ,\lambda _{m_{2}})$ be nonnegative weights, we get penalized if we violate the constraint (2) on the other hand if we want to maintain a linear objective, we may see that we are rewarded for satisfying the objective strictly. The above system is called the Lagrangian Relaxation of our original problem.