1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Feb 2 '16 at 3:33
  • $\begingroup$ In general, there is actually to believe it does not. Integer programming is NP-Hard in general, while linear programming is in $\sf P$. $\endgroup$ – Clement C. Feb 2 '16 at 3:38
  • $\begingroup$ 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. $\endgroup$ – theideasmith Feb 2 '16 at 3:39
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Clement C. Feb 2 '16 at 3:43
  • 1
    $\begingroup$ Yes, I agree with your comment regarding what NP-Hard means. You have perfectly clarified the point. By equivalent, I mean that optimizing over a set of integers or over its convex hull will give you the same solution. In other words, the optimal solution of an integer problem always lies on its convex hull (hence all the cutting planes methods which try to approximate the convex hull dynamically). $\endgroup$ – Kuifje Feb 2 '16 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.