IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v56y2013i3p573-597.html
   My bibliography  Save this article

A robust and efficient proposal for solving linear systems arising in interior-point methods for linear programming

Author

Listed:
  • María Gonzalez-Lima
  • Aurelio Oliveira
  • Danilo Oliveira

Abstract

We introduce an efficient and robust proposal for solving linear systems arising at each iteration of primal-dual interior-point methods for linear programming. Our proposal is based on the stable system presented by Gonzalez-Lima et al. (Comput. Opt. Appl. 44:213–247, 2009 ). Using similar techniques as those employed in the splitting preconditioner introduced by Oliveira and Sorensen (Linear Algebra Appl. 394:1–24, 2005 ) we are able to express the stable system matrix in block form such that the diagonal blocks are nonsingular diagonal matrices and the off-diagonal blocks are matrices close to zero when the iterates are close to the solution set of the linear programming problem. For degenerate problems a perturbation of the diagonal is added. We use a low-cost fixed iterative method to solve this system. Numerical experiments have shown that our approach leads to very accurate solutions for the linear programming problem. Copyright Springer Science+Business Media New York 2013

Suggested Citation

  • María Gonzalez-Lima & Aurelio Oliveira & Danilo Oliveira, 2013. "A robust and efficient proposal for solving linear systems arising in interior-point methods for linear programming," Computational Optimization and Applications, Springer, vol. 56(3), pages 573-597, December.
    • Handle: RePEc:spr:coopap:v:56:y:2013:i:3:p:573-597
    DOI: 10.1007/s10589-013-9572-5
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-013-9572-5
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-013-9572-5?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gondzio, Jacek, 1995. "HOPDM (version 2.12) -- A fast LP solver based on a primal-dual interior point method," European Journal of Operational Research, Elsevier, vol. 85(1), pages 221-225, August.
    2. Robert E. Bixby, 1992. "Implementing the Simplex Method: The Initial Basis," INFORMS Journal on Computing, INFORMS, vol. 4(3), pages 267-284, August.
    3. Maria Gonzalez-Lima & Hua Wei & Henry Wolkowicz, 2009. "A stable primal–dual approach for linear programming under nondegeneracy assumptions," Computational Optimization and Applications, Springer, vol. 44(2), pages 213-247, November.
    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. Milan Dražić & Rade Lazović & Vera Kovačević-Vujčić, 2015. "Sparsity preserving preconditioners for linear systems in interior-point methods," Computational Optimization and Applications, Springer, vol. 61(3), pages 557-570, July.

    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. Cosmin G. Petra & Florian A. Potra, 2019. "A homogeneous model for monotone mixed horizontal linear complementarity problems," Computational Optimization and Applications, Springer, vol. 72(1), pages 241-267, January.
    2. Stojkovic, Nebojsa V. & Stanimirovic, Predrag S., 2001. "Two direct methods in linear programming," European Journal of Operational Research, Elsevier, vol. 131(2), pages 417-439, June.
    3. Peter Kall & János Mayer, 2006. "Some insights into the solution algorithms for SLP problems," Annals of Operations Research, Springer, vol. 142(1), pages 147-164, February.
    4. Cosmin Petra & Mihai Anitescu, 2012. "A preconditioning technique for Schur complement systems arising in stochastic optimization," Computational Optimization and Applications, Springer, vol. 52(2), pages 315-344, June.
    5. A. Swietanowski, 1995. "A Modular Presolve Procedure for Large Scale Linear Programming," Working Papers wp95113, International Institute for Applied Systems Analysis.
    6. Jacek Gondzio & Roy Kouwenberg, 2001. "High-Performance Computing for Asset-Liability Management," Operations Research, INFORMS, vol. 49(6), pages 879-891, December.
    7. Kypreos, Socrates, 2005. "Modeling experience curves in MERGE (model for evaluating regional and global effects)," Energy, Elsevier, vol. 30(14), pages 2721-2737.
    8. Yuriy Stoyan & Georgiy Yaskov, 2012. "Packing congruent hyperspheres into a hypersphere," Journal of Global Optimization, Springer, vol. 52(4), pages 855-868, April.
    9. Gondzio, Jacek, 2016. "Crash start of interior point methods," European Journal of Operational Research, Elsevier, vol. 255(1), pages 308-314.
    10. Im, Haesol & Wolkowicz, Henry, 2023. "Revisiting degeneracy, strict feasibility, stability, in linear programming," European Journal of Operational Research, Elsevier, vol. 310(2), pages 495-510.
    11. Stanimirovic, Predrag S. & Stojkovic, Nebojsa V. & Kovacevic-Vujcic, Vera V., 2005. "Stabilization of Mehrotra's primal-dual algorithm and its implementation," European Journal of Operational Research, Elsevier, vol. 165(3), pages 598-609, September.
    12. G. Al-Jeiroudi & J. Gondzio, 2009. "Convergence Analysis of the Inexact Infeasible Interior-Point Method for Linear Optimization," Journal of Optimization Theory and Applications, Springer, vol. 141(2), pages 231-247, May.
    13. Kouwenberg, Roy, 2001. "Scenario generation and stochastic programming models for asset liability management," European Journal of Operational Research, Elsevier, vol. 134(2), pages 279-292, October.
    14. Milan Dražić & Rade Lazović & Vera Kovačević-Vujčić, 2015. "Sparsity preserving preconditioners for linear systems in interior-point methods," Computational Optimization and Applications, Springer, vol. 61(3), pages 557-570, July.
    15. J. Gondzio & F. N. C. Sobral, 2019. "Quasi-Newton approaches to interior point methods for quadratic problems," Computational Optimization and Applications, Springer, vol. 74(1), pages 93-120, September.
    16. Levent Tunçel & Henry Wolkowicz, 2012. "Strong duality and minimal representations for cone optimization," Computational Optimization and Applications, Springer, vol. 53(2), pages 619-648, October.
    17. Gondzio, Jacek & Kouwenberg, Roy & Vorst, Ton, 2003. "Hedging options under transaction costs and stochastic volatility," Journal of Economic Dynamics and Control, Elsevier, vol. 27(6), pages 1045-1068, April.
    18. Tsionas, Mike G., 2020. "A coherent approach to Bayesian Data Envelopment Analysis," European Journal of Operational Research, Elsevier, vol. 281(2), pages 439-448.
    19. Maros, Istvan & Haroon Khaliq, Mohammad, 2002. "Advances in design and implementation of optimization software," European Journal of Operational Research, Elsevier, vol. 140(2), pages 322-337, July.
    20. Spyros Kontogiorgis, 2000. "Practical Piecewise-Linear Approximation for Monotropic Optimization," INFORMS Journal on Computing, INFORMS, vol. 12(4), pages 324-340, November.

    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:spr:coopap:v:56:y:2013:i:3:p:573-597. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.