# Why is integer programming more difficult than (real) linear programming? [duplicate]

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.

• (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. Mar 2 '18 at 12:27
• Also real linear programming can be reduced to SAT, isnt it ? Mar 2 '18 at 12:30
• 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). Mar 2 '18 at 12:36
• @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." Mar 2 '18 at 14:26
• @Shaull Your first comment seems more likely an answer. Mar 3 '18 at 17:15