# LP relaxation for ILP\IP (integer linear programming)

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

-

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
@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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 13, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9006178379058838, "perplexity_flag": "head"}