Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a lower bound for the ILP. Why this is correct?

I do understand that a feasible solution for the ILP is a feasible solution to the LP, and the reversed is not always so, i.e. a feasible solution for the LP is not necessarily a feasible solution for the ILP.

Can one please point out and explain briefly why it is so?

share|improve this question
add comment

1 Answer

As you say, a feasible solution for the ILP is a feasible solution for the LP. So if the LP has an optimal solution with objective value $\alpha$, this implies there is no feasible solution for the LP with objective value $< \alpha$, and in particular no feasible solution for the ILP with objective value $<\alpha$. That's what it means for $\alpha$ to be a lower bound for the ILP.

share|improve this answer
    
thank you for your answer, but i still do not get it... why it is a lower bound rather than an upper bound? could you please elaborate on it a little bit more? –  user36774 Jul 29 '12 at 19:29
    
"this implies there is no feasible solution for the LP with objective value < alpha". Doesn't it define a different goal function, which it's optimum might exist? –  user36774 Jul 29 '12 at 19:35
1  
@user36774: it's a lower bound because this is a minimization problem. –  Robert Israel Jul 29 '12 at 22:50
    
For example, take this simple ILP: minimize $2 x$ subject to $2 x \ge 3$, $x$ an integer. Leaving out the "integer" requirement, the linear programming problem has optimal solution $x=3/2$ with objective value $3$. That says there is no real solution with $2x < 3$, and therefore no integer solution with $2x < 3$, so $3$ is a lower bound on the objective values for the ILP. Of course the actual optimal solution for the ILP has objective value $4$ in this case. –  Robert Israel Jul 29 '12 at 22:56
    
Maybe I am wrong, but x=2 is a feasible solution for the ILP, so why do you say that the optimal solution for the ILP has an objective value of 4? –  user36774 Jul 30 '12 at 5:17
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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