# Linear Relaxation vs Lagrangian Relaxation

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).

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).