3
$\begingroup$

Why is integer programming (IP) more difficult than (real) linear programming (LP)?

I searched a lot on the web, but I didn't find an answer.

$\endgroup$
7
  • 1
    $\begingroup$ (real) Linear Programming can be solved in polynomial time, whereas Integer Linear Programming can be very easily reduced to from SAT, making it NP-hard (it can actually be shown to be NP complete, but this is less trivial). Thus, if $P\neq NP$, then LP is easier (computationally) than ILP. $\endgroup$ – Shaull Mar 2 '18 at 12:27
  • $\begingroup$ Also real linear programming can be reduced to SAT, isnt it ? $\endgroup$ – Qwerto Mar 2 '18 at 12:30
  • $\begingroup$ It can, but it's not very easy. It basically amounts to proving that the problem is NP, for which you need to show that the solutions are not too big (so that they can be represented in polynomially many bits). $\endgroup$ – Shaull Mar 2 '18 at 12:36
  • $\begingroup$ @Shaull To me, the question is asking what features of integer linear programming make it harder than real linear programming. Answering "ILP is harder because you can reduce hard problems to it" is a bit like saying "Warren Buffett is richer than you because he has more money." $\endgroup$ – David Richerby Mar 2 '18 at 14:26
  • 1
    $\begingroup$ @Shaull Your first comment seems more likely an answer. $\endgroup$ – xskxzr Mar 3 '18 at 17:15
1
$\begingroup$

Given a starting solution, the Simplex algorithm will systematically find solutions with better values of your goal function. However, it runs using real numbers (or rational numbers). You can use the Simplex algorithm to find a solution for an integer programming problem that is optimal, except that it ignores the need for integer values.

Lets say you have a solution where a variable x has a value of x = 1000.525. Clearly that's not an acceptable solution. So you take your system, make two copies, and in one copy you add the condition x ≤ 1000, in the other you add the condition x ≥ 1001. You solve both copies of the problem, but then you have other non-integer values and you go on.

So starting with your non-integer solution, you have many, many ways to try to turn them into integer solutions.

The smaller the numbers, the worse it gets. In that example I gave, you'd expect that the solution doesn't change a lot. If you have a solution x = 0.7, you add the equation x = 0 or x ≥ 1, and that can make a massive change.

$\endgroup$
3
  • $\begingroup$ While you show that starting from a real solution it could be difficult to reach an integer solution, you do not argue why this real solution is easier to get in the first place! So, I feel your argument is a bit incomplete. However, completing this argument might not be easy, as there are well known cases where integer programming is in fact 'easy' (e.g. when we have a totally uni-modular matrix describing the LP) $\endgroup$ – Discrete lizard Mar 2 '18 at 18:31
  • $\begingroup$ You showed it is difficult to reach an integer solution from a real solution, but one may find an integer solution directly. So your argument is not sufficient. $\endgroup$ – xskxzr Mar 3 '18 at 17:13
  • 1
    $\begingroup$ One note: simplex algorithm is exponential in worst case, so it is nowhere near the real explanation. $\endgroup$ – rus9384 Mar 3 '18 at 19:23

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