3 ms·
Simplex algorithm should never work given its exponential worst case performance. Yet it solves the vast majority of LP problems, including ones with billions o
by whatever1 2y ago
Simplex algorithm should never work given its exponential worst case performance. Yet it solves the vast majority of LP problems, including ones with billions of variables. It is the default algorithm for every solver despite the fact that we have a polynomial interior point method in our disposal. Go figure.
Worst case performance or NP completeness is not a predictor of how fast we can solve an optimization problem.
- JohnKemeny 2y ago> should never work given its exponential worst case performance This is again not true. We know why it works well. See the paper "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time" by Spielmann and Teng.
- whatever1 2y agoWe started understanding of why it works so well like 30 years after its first implementation (in the 1950's)? The paper you mention is written in the 2000s while the Simplex dominated the field from at least the 70's. Meanwhile the GP would have discarded the simplex algorithm due to its worst case performance.
- SkiFire13 2y ago> Simplex algorithm should never work given its exponential worst case performance. Note that it has been proven however that if you slightly perturbate the inputs then the expected complexity becomes polynomial, meaning the inputs for which it's exponential are actually just pathological cases and it is polynomial in practice.
- FooBarBizBazz 2y agoMan, there was a lot of obtuse argument to wade through to get to this post. This is an interesting fact. Apparently this is the source? https://arxiv.org/abs/cs/0111050 https://arxiv.org/abs/cs/0111050