A Redundant Klee-Minty Construction with All the Redundant Constraints Touching the Feasible Region

By introducing some redundant Klee-Minty constructions, we have previously shown that the central path may visit every vertex of the Klee-Minty cube having $2^n-2$ ``sharp'' turns in dimension $n$. In all of the previous constructions, the maximum of the distances of the redundant constraints to the corresponding facets is an exponential number of the dimension $n$, and those distances are decaying geometrically. In this paper, we provide a new construction in which all of the distances are set to zero, i.e., all of the redundant constraints touch the feasible region.

Citation

McMaster University, January 2008.

Article

Download

View A Redundant Klee-Minty Construction with All the Redundant Constraints Touching the Feasible Region