# What is the difference between linear and integer programming?

Recently I tried to solve a maximization integer programming problem using linear programming by flooring the max point - but got the wrong answer. I'm wondering if someone can explain mathematically why what I did is wrong. I have an underlying intuition but cannot express it mathematically.

• In general there's just no reason to expect that rounding the solution to an optimization problem gives you a solution to the same optimization problem over the integers. The integer points among all points could be distributed in a very weird way (with respect to the function you're optimizing), e.g. avoiding all of the local optima. – Qiaochu Yuan Feb 2 '16 at 3:33
• In general, there is actually to believe it does not. Integer programming is NP-Hard in general, while linear programming is in $\sf P$. – Clement C. Feb 2 '16 at 3:38
• That's what I realize. It was a lack of thinking/understanding that brought me to doing this. That is why I'm trying to understand how to get the right solution. – theideasmith Feb 2 '16 at 3:39

• I am not sure I understand your last paragraph -- what do you mean by "is equivalent" (in which sense?). Also, as a nitpick: NP-Hard does not mean that no poly-time algorithm exists (otherwise, we would have $\sf P\neq \sf NP$ proven). It just means we do not know any general poly-time algorithm to solve arbitrary integer programs, and strongly suspect there is none. – Clement C. Feb 2 '16 at 3:43