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.
Similar content being viewed by others
Notes
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
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
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
Bunch JR, Parlett BN (1971) Direct methods for solving symmetric indefinite systems of linear equations. SIAM J Numer Anal 8:639–655
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
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
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
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
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
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
Gondzio J (2012) Interior point methods 25 years later. Eur J Oper Res 218:587–601
Jones MT, Plassmann PE (1995) An improved incomplete Cholesky factorization. ACM Trans Math Softw 21:5–17
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
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
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
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
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
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
Corresponding author
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
About this article
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
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-018-0370-x
Keywords
- Hybrid preconditioners
- Iterative methods
- Interior point methods
- Linear programming
- Splitting preconditioner