> It still boggles my mind how simplex, something that theoretically runs worse that interior point methods is competitive (at least based on what I've read online). I guess with these problems, the instances of the problem has a huge effect on how long approaches take.
Well, theoretical worst cases are just that. They are worst case bounds. People think NP-hard problem are intractable, but this is a misunderstanding. Many NP-hard problems can actually be solved with fairly good average case performance.
Case in point: the Simplex method is worst-case exponential time, but its average case performance is actually pretty good.
When Khachiyan first came up with his elipsoid method, it was polynomial time but in practice it was too slow. Karmarkar's interior point algorithm was polynomial time too, but performs much efficiently.
These days though, solve times are predominantly affected by solver heuristics and randomness. The choice of Simplex vs Interior Point does not make a significant difference in many cases.
Well, theoretical worst cases are just that. They are worst case bounds. People think NP-hard problem are intractable, but this is a misunderstanding. Many NP-hard problems can actually be solved with fairly good average case performance.
Case in point: the Simplex method is worst-case exponential time, but its average case performance is actually pretty good.
When Khachiyan first came up with his elipsoid method, it was polynomial time but in practice it was too slow. Karmarkar's interior point algorithm was polynomial time too, but performs much efficiently.
These days though, solve times are predominantly affected by solver heuristics and randomness. The choice of Simplex vs Interior Point does not make a significant difference in many cases.