Lagrangian relaxation
From Wikipedia, the free encyclopedia
Lagrangian relaxation is a relaxation technique which works by moving hard constraints into the objective and punish the objective if they are not satisfied.
[edit] Mathematical description
Given an LP problem 
and 
on the following form:
-
max cTx s.t. 
If we split the constraints in A such that 
, 
and m1 + m2 = m we may write the system:
-
max cTx s.t. (1) 
(2) 
We may introduce the constraint (2) into the objective:
-
max cTx + λT(b2 − A2x) s.t. (1)
If we let 
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.
