The Efficiency of the Simplex Method: A Survey (Q3753810)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3991278
Language Label Description Also known as
default for all languages
No label defined
    English
    The Efficiency of the Simplex Method: A Survey
    scientific article; zbMATH DE number 3991278

      Statements

      The Efficiency of the Simplex Method: A Survey (English)
      0 references
      0 references
      1987
      0 references
      practical experience
      0 references
      Monte-Carlo methods
      0 references
      simplex method
      0 references
      survey
      0 references
      upper and lower bounds
      0 references
      probabilistic analysis
      0 references
      The linear programming problem is by far the most widely used optimization model. Its impact on economic and government modeling is immense. The simplex method for solving the linear programming (LP) problem, due to George Dantzig, has been an extremely efficient computational tool for almost four decades. The method has been the subject of intense investigations for many years, but some aspects of its behavior are not fully understood yet. The purpose of this paper is to survey the body of knowledge on the efficiency of the simplex method, from both practical and theoretical points of view. Adopting the number of iterations (pivot steps) as the yardstick for efficiency, we survey four aspects of the issue: (1) Reports on practical experience of the method's performance on real-life LP problems. (2) Results on controlled (Monte-Carlo) experiments solving LP problems which were randomly generated according to some predetermined distributions. (3) Complexity results, including theoretical analyses on both upper and lower bounds for the performance of the simplex as well as non-simplex algorithms for LP. (4) Results of recent theoretical studies using probabilistic analysis to derive bounds on the average behavior of the simplex method. We discuss the consequences and limitations of the various studies. Special emphasis is given to open questions.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references