Let's say we are using Integer Programming in order to minimize an objective function. We are interested in computing a lower bound for the problem.
My question is: when should we use a Linear Programming relaxation, and when should we use a Lagrangian relaxation? Is there some intuition in when one relaxation would be better than the other? In particular, consider the situation in which there are no specific "complicating" constraints in the problem (e.g. all the constraints seem equally important).
Best Answer
Let $z*$ be the optimal solution of the integer problem, $z_{Lin}$ be the solution of the linear relaxation, and $z_{Lag}$ be the solution of the Lagrangian relaxation. For a minimization problem, the following inequalities hold: $$ z*\ge z_{Lag} \ge z_{Lin} $$
In other words, the Lagrangian relaxation is tighter than the Linear relaxation. $z_{Lag}$ and $z_{Lin}$ are equal if the Lagrangian relaxation verifies what is called the integrality property (when relaxing the integer variables does not affect the solution).
So in general, if the Lagrangian relaxation does not verify the integrality property, it will yield a better solution than the linear relaxation. If it does verify the integrality property, than both relaxations will give the same result, but since the linear relaxation is much simpler to compute, there is no point of using the Lagrangian relaxation.