Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. 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
1  
we do not really do tutorials here. Try math.stackexchange.com/questions?page=4&sort=newest –  Will Jagy Jul 29 '12 at 19:26
    
I expected one to share his\her knowledge, and not an answer as you did. How a math junior can become a senior, when the senior is afraid to share the knowledge it holds?! That was a rhetorical question, thank you anyway. –  user25407 Jul 29 '12 at 19:32
    
Posted at math.stackexchange.com/questions/176559/… –  Will Jagy Jul 29 '12 at 19:58
    
correct, since you did not help. and you continue not to help. are you a cop or a mentor? –  user25407 Jul 29 '12 at 20:05
3  
Welcome to MathOverflow, and thank you for letting those of us who have been here for years know that you, born yesterday, know we are doing it all wrong. But please have a look at our faq to get some kind of idea as to what we think the purpose of this particular website is. –  Gerry Myerson Jul 29 '12 at 23:14
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.