[rich_sasha]

Simplex AFAIK isn’t used to solve real world “regular” linear programs as worst-case complexity is exponential, and polynomial algorithms exist.

As it happens, MILP solvers often do use the simplex solver internally, as it can be hot-restarted - you can modify the problem a bit and quickly get an amended solution.

[wenc]

On the contrary the simplex method IS used to solve regular linear programs, despite the existence of polynomial time barrier/interior-point algorithms.

Yes, simplex is worst case exponential and barrier is worst-case polynomial, but depending on the problem, the average case characteristics are very different. Depending on the problem, simplex can beat barrier methods. For many large LP/MILP problems, heuristics and randomness usually dominate solution time rather than simplex vs barrier. That’s why commercial solvers so thoroughly beat open-source solvers —- their heuristics are far superior.

For NP-hard problems, it’s not a good idea to judge algorithms by their worst-case complexity —- which only provides bound — but by their real world performance. Before Karmarkar’s method, there was another polynomial time algorithm by Khachiyan. Despite being polynomial time, it was too slow to be of any practical interest.