Linear programming (LP) is a mature discipline of optimization. It is of great importance both in theory and in practice, namely due to the fact that most optimization problems solved in business and industry are formulated as mixed-integer LPs. The solution methods for them require efficient LP algorithms as the crucial subroutine. Still, LP is a source of difficult open problems in theory, remaining unsolved for a long time. Namely, it is the problem of computational complexity of the Simplex Algorithm (SA). The question is whether there exists a pivotage strategy making SA work in polynomial time. A positive answer, under further assumptions, would settle another important problem whether or not LP has a strongly polynomial algorithm. All of the currently known efficient algorithms, such as Khachyian’s Ellipsoid Method (which is polynomial in theory but hard-to-implement in practice) or Interior Point Methods (which are efficient both in theory and in practice) are weakly polynomial only, meaning that their iteration bounds depend on the so-called Big-L measure of the size of input data. We also point out some recent results on the polynomial version of the Hirsch hypothesis, which plays an essential role in the analysis of SA and is a long-standing open problem in polyhedral geometry. And, finally, we will summarize some results on the average-time complexity of SA, trying to explain why the difficult instances for SA, such as Klee-Minty’s LPs, seem to occur so rarely.

Michal Černý is a full professor of Econometrics & Operations Research at Department of Econometrics, University of Economics, Prague, Czech Republic. He graduated from Faculty of Mathematics and Physics, Charles University, Prague and Faculty of International Relations, University of Economics, Prague. His research interests include special optimization problems, optimization problems with inexact inputs, optimization problems in statistics and statistical analysis of special kinds of data (such as streaming data or interval-valued data). He currently works on the CSF grant project Financial data streams and related identification and optimization problems.