0
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ we do not really do tutorials here. Try math.stackexchange.com/questions?page=4&sort=newest $\endgroup$
    – Will Jagy
    Jul 29, 2012 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, 2012 at 19:32
  • $\begingroup$ Posted at math.stackexchange.com/questions/176559/… $\endgroup$
    – Will Jagy
    Jul 29, 2012 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, 2012 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, 2012 at 23:14

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.