ABSTRACT
Overview Although Dantzig’s simplex algorithm has proven to be very successful in solving LOmodels of practical problems, its theoretical worst-case behavior is nevertheless very bad. In 1972, Victor Klee (1925-2007) and George J. Minty (1929-1986) constructed examples for which the simplex algorithm requires an exorbitant amount of computer running time; see Chapter 9. The reason that the simplex algorithm works fast in practice is that LOmodels arising from most practical problems are usually so-called ‘average’ problems and are fortunately not the rare ‘worst-case’ problems. Besides the theoretical question whether or not there exists a fast algorithm that solves large-scale linear optimization problems, also the practical need for such an ecient algorithm has inspired researchers to try to answer this question.
