Beyond Worst-Case Complexity of the Simplex Method
Name
Mihkel Uutar
Abstract
This thesis investigates the performance of the Simplex Method beyond its theoretical worst-case by empirically assessing the effect of input distributions on efficiency.The research consists of three experiments, which focus on different input distributions and an optimized pivoting rule, the Zero-Exploiting Simplex Method (ZESM). The results demonstrate that input distributions significantly affect performance with structured sparse requiring fewer operations compared to dense matrices. Implementing ZESM reduced the number of operations required by over 50% across various inputs. The research aims to provide a foundation for future research to optimize the Simplex Method based on input characteristics.
Graduation Thesis language
English
Graduation Thesis type
Bachelor - Computer Science
Supervisor(s)
Kallol Roy
Defence year
2024