SPEAKER

How difficult is a Linear Programming problem?

Abstract. It is well known that simplex method for solving Linear Programming (LP) problems introduced by George Dantzig in 1947 has exponential complexity. It means that the number of steps required for finding the optimal solution grows exponential together with the size of the problem.
In the late 70s L.Khachiyan shows that the ellipsoid method introduced independently by N.Shor and A. Nemirovski , D. Yudin has polynomial complexity. The ellipsoid method, however, was not able to compete with Simplex.
Therefore, in the mid-80s, after N.Karmarkar introduced his projective transformation method, the search for LP methods that are both polynomial and numerically efficient grew with unprecedented intensity. It leads to the Interior Point Theory and methods (IPMs). We discussed the basic IPM results. Then, we introduce Exterior Point Methods (EPMs) -an alternative to IPMs. The EPMs are based on the Nonlinear Rescaling (NR) theory. The NR approach allows to discover the "hot" start phenomenon, which leads to improved complexity for nondegenerate LP. We show new complexity results and illustrate it on a number real life LP.