Polynomial time algorithms have been known for linear programming for decades; _integer_ linear programming is NP-hard.
Continuous linear programming is also _hard_. Not in the sense of NP-hard, but in the sense of there being lots of algorithmic and engineering aspects that go into an efficient, modern LP solver. Even just the numerics are complicated enough.
(And many integer linear programming solvers are based on continuous linear programming solvers.)
I find this interplay between "traditional" mathematicians and those in allied fields like CS to be very interesting.
Modern concrete and steel (and plastics etc) allow you to build so much more advanced, but also simpler, than the kinds of wacky shenanigans people had to pull off in eg the 19th century just to get high pressure steam engines to work (if they could do that at all).