[pfdietz]

I thought there were other interior point methods now beside the ellipsoid algorithm that performed better. Some of these are useful in convex nonlinear programming, and I believe one is used (with a code generator from Stanford to make it faster) in the guidance software for landing the Falcon 9 first stage. There, as the stage descends it repeatedly solves the problem of reaching the landing point at zero velocity with minimum fuel use, subject to various constraints.

[luiwammus]

Yes, there are other interior point methods besides the ellipsoid method, and virtually all of them perform better for linear programming. Sometimes, the solvers will use these at the root node for very large models, as they can beat out the simplex algorithm. However, I am unsure if any of them has been proven to run in polynomial time, and if so, if the proof is significantly different from the proof for the ellipsoid method. The point I was mainly trying to make is that there can be a significant gap between practice and theory for ILP. Even 40 years after LP was proven to be polytime solvable, simplex remains the most widely used method, and it is very hard for other methods to catch up.

[pfdietz]

Karmarkar's algorithm, for example, has been proved to run in polynomial time.

https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm

It was also (in)famous as an algorithm that was patented (the patent expired in 2006).