When I hear linear programming I always remember this method https://en.wikipedia.org/wiki/Ellipsoid_method. It is nice example of algorithm which is not useful for programming only for mathematicians (I believe it was used as proof that linear programming is in P). I think that most of the programmers will have really hard time to implement it and also it is on average slower than simplex method despite a fact that simplex is not in P and this algorithm is.
It's been a while since I studied mathematics (and I wrote my thesis in optimization), but at the time it was not clear if simplex is in P or not. I think no one has found a selection function for variables that is always polynomial.
I vaguely recall that Soviet planners used something based on n-dimensional ellipsoids (instead of Simplex) to optimize resources allocations of Aereoflot flights but I cannot remember anything more specific, alas.
(I read this on the magazine of my country's equivalent of ACM in '80s and it somehow stuck with me all these years)
