Skip to main content
Log in

Using groups in the splitting preconditioner computation for interior point methods

  • Research Paper
  • Published:
4OR Aims and scope Submit manuscript

Abstract

Interior point methods usually rely on iterative methods to solve the linear systems of large scale problems. The paper proposes a hybrid strategy using groups for the preconditioning of these iterative methods. The objective is to solve large scale linear programming problems more efficiently by a faster and robust computation of the preconditioner. In these problems, the coefficient matrix of the linear system becomes ill conditioned during the interior point iterations, causing numerical difficulties to find a solution, mainly with iterative methods. Therefore, the use of preconditioners is a mandatory requirement to achieve successful results. The paper proposes the use of a new columns ordering for the splitting preconditioner computation, exploring the sparsity of the original matrix and the concepts of groups. This new preconditioner is designed specially for the final interior point iterations; a hybrid approach with the controlled Cholesky factorization preconditioner is adopted. Case studies show that the proposed methodology reduces the computational times with the same quality of solutions when compared to previous reference approaches. Furthermore, the benefits are obtained while preserving the sparse structure of the systems. These results highlight the suitability of the proposed approach for large scale problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. The synonym “block” could be used instead of “group” to avoid connections with group theory. The word “group” was preferred for coherence with previous works in the area.

References

  • Al-Jeiroudi G, Gondzio J, Hall J (2008) Preconditioning indefinite systems in interior point methods for large scale linear optimisation. Optim. Methods Softw. 23(3):345–363

    Article  Google Scholar 

  • Bergamaschi L, Gondzio J, Venturin M, Zilli G (2007) Inexact constraint preconditioners for linear systems arising in interior point methods. Comput Optim Appl 36(1–2):137–147

    Article  Google Scholar 

  • Bocanegra S, Campos F, Oliveira A (2007) Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods. Spec Issue Comput Optim Appl 36(2/3):149–164

    Article  Google Scholar 

  • Bunch JR, Parlett BN (1971) Direct methods for solving symmetric indefinite systems of linear equations. SIAM J Numer Anal 8:639–655

    Article  Google Scholar 

  • Campos FF (1995) Analysis of conjugate gradients—type methods for solving linear equations. Ph.D. thesis, Oxford University Computing Laboratory, Oxford

  • Casacio L, Lyra C, Oliveira ARL, Castro CO (2017) Improving the preconditioning of linear systems from interior point methods. Comput Oper Res 85:129–138

    Article  Google Scholar 

  • Chai JS, Toh KC (2007) Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming. Comput Optim Appl 36(1–2):221–247

    Article  Google Scholar 

  • Czyzyk J, Mehrotra S, Wagner M, Wright SJ (1999) PCx an interior point code for linear programming. Optim Methods Softw 11–2(1–4):397–430

    Article  Google Scholar 

  • Dollar HS, Gould NIM, Schilders WHA, Wathen AJ (2007) Using constraint preconditioners with regularized saddle-point problems. Spec Issue Comput Optim Appl 36(2/3):249–270

    Article  Google Scholar 

  • Dražić MD, Lazović RP, Kovačević-Vujčić VV (2015) Sparsity preserving preconditioners for linear systems in interior-point methods. Comput Optim Appl 61(3):557–570

    Article  Google Scholar 

  • Ghidini CTLS, Oliveira ARL, Sorensen DC (2014) Computing a hybrid preconditioner approach to solve the linear systems arising from interior point methods for linear programming using the gradient conjugate method. Ann Manag Sci 3:43–64

    Article  Google Scholar 

  • Gondzio J (2012) Interior point methods 25 years later. Eur J Oper Res 218:587–601

    Article  Google Scholar 

  • Jones MT, Plassmann PE (1995) An improved incomplete Cholesky factorization. ACM Trans Math Softw 21:5–17

    Article  Google Scholar 

  • Mehrotra S (1992) Implementations of affine scaling methods: approximate solutions of systems of linear equations using preconditioned conjugate gradient methods. ORSA J Comput 4:103–118

    Article  Google Scholar 

  • Monteiro RD, O’Neil JW, Tsuchiya T (2005) Uniform boundedness of a preconditioned normal matrix used in interior point methods. SIAM J Optim 15(1):96–100. https://doi.org/10.1137/S1052623403426398

    Article  Google Scholar 

  • Oliveira ARL, Sorensen DC (2005) A new class of preconditioners for large-scale linear systems from interior point methods for linear programming. Linear Algebra Appl 394:1–24

    Article  Google Scholar 

  • Sunagua P, Oliveira ARL (2017) A new approach for finding a basis for the splitting preconditioner for linear systems from interior point methods. Comput Optim Appl 67:111–127

    Article  Google Scholar 

  • Velazco MI, Oliveira ARL, Campos FF (2010) A note on hybrid preconditions for large scale normal equations arising from interior-point methods. Optim Methods Softw 25:321–332

    Article  Google Scholar 

Download references

Acknowledgements

The authors would like to thank FAPESP (Fundação de Amparo a Pequisa do Estado de São Paulo) and CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico) for their support.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Luciana Casacio.

Ethics declarations

Conflicts of interest

All authors declare that they have no conflict of interest.

Ethical standard

This article does not contain any studies with human participants or animals performed by any of the authors.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Casacio, L., Oliveira, A.R.L. & Lyra, C. Using groups in the splitting preconditioner computation for interior point methods. 4OR-Q J Oper Res 16, 401–410 (2018). https://doi.org/10.1007/s10288-018-0370-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10288-018-0370-x

Keywords

Mathematics Subject Classification

Navigation