Has anyone ever heard of the Klee-Minty Cube in Optimization?
Supposedly, the Klee-Minty Cube shows the "flaws" of the Dantzig's Simplex Algorithm. Supposedly, Dantzig's Simplex Algorithm is unable to optimize (i.e. find optimal values in the feasible ranges given some function and constraints) the Klee-Minty Cube in polynomial time, thus showing the "worst case" of the Simplex Algorithm.
My Question: Does anyone know why Dantzig's Simplex Algorithm struggles to optimize the Klee-Minty Cube? What kind of obstacles does the Klee-Minty Cube present, such that the Simplex Algorithm is unable to optimize this problem in polynomial time?
Can someone please comment on this?
Thanks!
References: