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

Eissa Nematollahi(nematoemcmaster.ca)
Tamas Terlaky(terlakymcmaster.ca)

Abstract: 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.

Keywords: Linear optimization, Klee-Minty cube, interior point methods, redundant, central path.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: McMaster University, January 2008.

Download: [PDF]

Entry Submitted: 01/05/2008
Entry Accepted: 01/05/2008
Entry Last Modified: 01/05/2008

Modify/Update this entry