What is the difference between linear and integer programming?

Question

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.

Answer 1

If your variables are integer, the constraints do not form a convex set. Indeed, if you just consider two integers, then all points between these integers are not part of the set, therefore it is not convex.

This has important consequences, as convexity is an important property in optimization: it guarantees that any local minimum is a global one. Loosing this property makes integer optimization harder.

However, this difficulty can be delt with by showing that working on integers is equivalent to working on the convex hull of integers, which is convex. But integer programming remains NP-hard (no polynomial algorithm can solve an integer program), whereas linear programming is polynomial time computable.