IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v33y1987i3p301-334.html
   My bibliography  Save this article

The Efficiency of the Simplex Method: A Survey

Author

Listed:
  • Ron Shamir

    (Department of Computer Science, School of Mathematics, Tel Aviv University, Tel Aviv, Israel)

Abstract

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 major 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.

Suggested Citation

  • Ron Shamir, 1987. "The Efficiency of the Simplex Method: A Survey," Management Science, INFORMS, vol. 33(3), pages 301-334, March.
    • Handle: RePEc:inm:ormnsc:v:33:y:1987:i:3:p:301-334
    DOI: 10.1287/mnsc.33.3.301
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.33.3.301
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.33.3.301?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jesús Latorre & Santiago Cerisola & Andrés Ramos & Rafael Palacios, 2009. "Analysis of stochastic problem decomposition algorithms in computational grids," Annals of Operations Research, Springer, vol. 166(1), pages 355-373, February.
    2. Syed Inayatullah & Nasir Touheed & Muhammad Imtiaz, 2015. "A Streamlined Artificial Variable Free Version of Simplex Method," PLOS ONE, Public Library of Science, vol. 10(3), pages 1-28, March.
    3. Drexl, Andreas & Kimms, Alf, 1998. "Optimization guided lower and upper bounds for the resource investment problem," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 481, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    4. Antimo Barbato & Antonio Capone, 2014. "Optimization Models and Methods for Demand-Side Management of Residential Users: A Survey," Energies, MDPI, vol. 7(9), pages 1-38, September.
    5. T. L. Morin & N. Prabhu & Z. Zhang, 2001. "Complexity of the Gravitational Method for Linear Programming," Journal of Optimization Theory and Applications, Springer, vol. 108(3), pages 633-658, March.
    6. Ordónez, Fernando & Freund, Robert M., 2003. "Computational Experience and the Explanatory Value of Condition Numbers for Linear Optimization," Working papers 4337-02, Massachusetts Institute of Technology (MIT), Sloan School of Management.
    7. Bahman Kalantari, 2015. "A characterization theorem and an algorithm for a convex hull problem," Annals of Operations Research, Springer, vol. 226(1), pages 301-349, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:33:y:1987:i:3:p:301-334. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.