Prof. Roman A. Polyak

George Mason University, USA

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.

Plenary Speakers

Prof. Roman A. Polyak
George Mason University, USA
Prof. Srinivas Chakravarthy
Kettering University, Flint, USA
Prof. Arkadii Chikrii
V. M. Glushkov Institute of Cybernetics, Kyiv, Ukraine
Prof. Boris S. Mordukhovich
Wayne State University, Detroit, USA
Prof. Janusz Kacprzyk
Warsaw University of Technology, Poland
Prof. Yedilkhan Amirgaliyev
Institute of Information and Computing Technologies, Almaty, Kazakhstan
Prof. Adil Bagirov
Centre for Smart Analytics, Institute of Innovation, Science and Sustainability, Federation University Australia, Australia
Prof. Rza Bashirov
Eastern Mediterranean University, Turkey
Prof. Refail Kasimbeyli
Eskişehir Technical University, Türkiye
Prof. Agasi Melikov
Institute of Control Systems, Ministry of Science and Education, Azerbaijan
Prof. Mais Farkhadov
Institute of Control Sciences of RAS, Russia