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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.