By introducing redundant Klee-Minty examples, we have previously shown that the central path can be bent along the edges of the Klee-Minty cubes, thus having $2^n-2$ sharp turns in dimension $n$. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler and more powerful construction, where the redundant constraints are parallel with the coordinate-planes. An important consequence of this new construction is that one of the sets of redundant hyperplanes is touching the feasible region, and $N$, the total number of the redundant hyperplanes is reduced by a factor of $n^2$, further tightening the gap between iteration-complexity upper and lower bounds.
Citation
Report Number: AdvOL2006/12, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Article
View A Simpler and Tighter Redundant Klee-Minty Construction