Simplex Solver Software: Rules of Thumb
Worse-case performance is exponential in the size of the problem being solved, but empirically it works well.
- Simplex has polynomial “quasi-worse case” complexity
For a problem with m rows and n columns
- Average number of iterations to reach a solution is 2m.
- Upper bound on iterations is about 2(m+n)
- Total computational time increases roughly in the order of m-cubed.
- 1K-constraint problem may require 1M times as much computational time as a 10-constraint problem