Linear programming as it's usually defined allows for the solution to involve arbitrary real numbers, and it's that flexibility that allows general LPs to be solved in polynomial time. The restriction to integers turns this into an integer programming problem, which is NP-Complete. Though that doesn't seem to bother Mathematica (which presumably has a similar sort of constraint solver working under the hood). :-)