Using groups in the splitting preconditioner computation for interior point methods

• Published in: 4OR 2018-12, Vol.16 (4), p.401-410
• Main Authors: Casacio, Luciana, Oliveira, Aurelio R. L., Lyra, Christiano
• Format: Article
• Language: English
• Subjects: Business and Management; Cholesky factorization; Columns (structural); Conditioning; Industrial and Production Engineering; Iterative methods; Linear programming; Linear systems; Matrix methods; Operations research; Operations Research/Decision Theory; Optimization; Preconditioning; Queuing theory; Research Paper; Robustness (mathematics); Splitting
• ISSN: 1619-4500; 1614-2411
• DOI: 10.1007/s10288-018-0370-x

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.