IDEAS home Printed from https://ideas.repec.org/p/mit/sloanp/3547.html
   My bibliography  Save this paper

Computational Experience and the Explanatory Value of Condition Numbers for Linear Optimization

Author

Listed:
  • Ordónez, Fernando
  • Freund, Robert M.

Abstract

The goal of this paper is to develop some computational experience and test the practical relevance of the theory of condition numbers C(d) for linear optimization, as applied to problem instances that one might encounter in practice. We used the NETLIB suite of linear optimization problems as a test bed for condition number computation and analysis. Our computational results indicate that 72% of the NETLIB suite problem instances are ill-conditioned. However, after pre-processing heuristics are applied, only 19% of the post-processed problem instances are ill-conditioned, and log C(d) of the finitely-conditioned post-processed problems is fairly nicely distributed. We also show that the number of IPM iterations needed to solve the problems in the NETLIB suite varies roughly linearly (and monotonically) with log C(d) of the post-processed problem instances. Empirical evidence yields a positive linear relationship between IPM iterations and log C(d) for the post-processed problem instances, significant at the 95% confidence level. Furthermore, 42% of the variation in IPM iterations among the NETLIB suite problem instances is accounted for by log C(d) of the problem instances after pre-processin

Suggested Citation

  • 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.
    • Handle: RePEc:mit:sloanp:3547
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/1721.1/3547
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Freund, Robert Michael. & Todd, Michael J., 1947-, 1992. "Barrier functions and interior-point algorithms for linear programming with zero-, one-, or two-sided bounds on the variables," Working papers 3454-92., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    2. Sharon Filipowski, 1997. "On the Complexity of Solving Sparse Symmetric Linear Programs Specified with Approximate Data," Mathematics of Operations Research, INFORMS, vol. 22(4), pages 769-792, November.
    3. Ron Shamir, 1987. "The Efficiency of the Simplex Method: A Survey," Management Science, INFORMS, vol. 33(3), pages 301-334, March.
    4. Robert M. Freund & Michael J. Todd, 1995. "Barrier Functions and Interior-Point Algorithms for Linear Programming with Zero-, One-, or Two-Sided Bounds on the Variables," Mathematics of Operations Research, INFORMS, vol. 20(2), pages 415-440, May.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Cheung, Dennis & Cucker, Felipe & Pea, Javier, 2009. "On strata of degenerate polyhedral cones I: Condition and distance to strata," European Journal of Operational Research, Elsevier, vol. 198(1), pages 23-28, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Robert M. Freund & Jorge R. Vera, 2003. "On the Complexity of Computing Estimates of Condition Measures of a Conic Linear System," Mathematics of Operations Research, INFORMS, vol. 28(4), pages 625-648, November.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Robert M. Freund & Fernando Ordóñez, 2005. "On an Extension of Condition Number Theory to Nonconic Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 30(1), pages 173-194, February.
    7. 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.
    8. Freund, Robert & Ordonez, Fernando, 2003. "On an Extension of Condition Number Theory to Non-Conic Convex Optimization," Working papers 4286-03, Massachusetts Institute of Technology (MIT), Sloan School of Management.
    9. 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.

    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:mit:sloanp:3547. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: None (email available below). General contact details of provider: https://edirc.repec.org/data/ssmitus.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.