The Klee-Minty cube is a well-known worst case example for which the simplex method takes an exponential number of iterations as the algorithm visits all the $2^n$ vertices of the $n$-dimensional cube. While such a behavior is excluded by polynomial interior point methods, we show that, by adding an exponential number of redundant inequalities, the central path can be bended along the edges of the Klee-Minty cube. More precisely, for an arbitrary small $\delta$, starting from the $\delta$-neighborhood of a vertex adjacent to the optimal solution, the central path takes $2^{n}-2$ turns as it passes through the $\delta$-neighborhood of all the vertices of the cube before converging to the optimal solution. In other words, central path-following interior point methods visit the neighborhood of all the vertices of the Klee-Minty cube in the same order as the simplex method visits its vertices.

Information: