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?

  • 1
    $\begingroup$ we do not really do tutorials here. Try math.stackexchange.com/questions?page=4&sort=newest $\endgroup$ – Will Jagy Jul 29 '12 at 19:26
  • $\begingroup$ 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. $\endgroup$ – user25407 Jul 29 '12 at 19:32
  • $\begingroup$ Posted at math.stackexchange.com/questions/176559/… $\endgroup$ – Will Jagy Jul 29 '12 at 19:58
  • $\begingroup$ correct, since you did not help. and you continue not to help. are you a cop or a mentor? $\endgroup$ – user25407 Jul 29 '12 at 20:05
  • 3
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jul 29 '12 at 23:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.