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

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.