You have to find the integers that fulfill a certain condition best. That's fundamentally different from real numbers. It looks exactly like other numerical problems, but there's no general solution for it, only (very good) heuristics for specific classes.
As nullc mentioned, the simplex method can take exponential time in some pathological examples (a space of measure 0, if that matters). The first P-time linear programming algo (and proof) was the ellipsoid method of Khachian in the 1980s. I have the impression it wasn't really practical. A later P-time interior-point method by Karmarkar is used sometimes today (it beats simplex on certain types of problems) from what I understand. But, I'm nowhere near expert in this area.
Even continuous linear programming wasn't known to be in P-time until the 1980s or so.