Klee-Minty cubes and the central path

  • Date: 10/25/2007

Tamás Terlaky (McMaster University)


University of Calgary


We consider a family of LO problems over the n-dimensional Klee-Minty
cube and show that the central path may visit all of its vertices in
the same order as simplex methods do. This is achieved by carefully
adding an exponential number of redundant constraints that forces the
central path to take at least 2^n-1 sharp turns. This fact suggests
that any feasible path-following IPM will take at least 2^n iterations
to solve this problem. This construction exhibits the worst-case
iteration-complexity of IPMs. In addition, we discuss some implications
for the curvature of the central path.
Joint work with: Antoine Deza, Eissa Nematollahi, Reza Peyghami and Yuriy Zinhenko.

Other Information: 

PIMS Distinguished Lecture 2007