Abstract
The linear systems arising from interior point methods (IPM) for linear programming are solved using the preconditioned conjugate gradient method (PCG). Two preconditioners are adopted: the controlled Cholesky factorization (CCF) of the normal equations system and the splitting preconditioner. The CCF performance depends upon the previous reordering of the linear programming constraint matrix rows. A comparison among two different reordering methods is performed in order to verify the most suitable one for this approach. Variants of nested dissection (ND) and the minimum degree (MD) are among the considered heuristics. Computational experiments with large-scale linear programming problems from several collection sets are performed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Silva, D., Velazco, M., & Oliveira, A. (2017). Influence of matrix reordering on the performance of iterative methods for solving linear systems arising from interior point methods for linear programming. Mathematical Methods of Operations Research, 85(1), 97–112.
Bocanegra, S., Campos, F., & Oliveira, A. (2007). Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods. Computational Optimization and Applications, 36, 149–167.
Velazco, M., Oliveira, A., & Campos, F. (2010). A note on hybrid preconditioners for large-scale normal equations arising from interior point methods. Optimization Methods and Software, 25(2), 321–332.
Benzi, M. (2002). Preconditioning techniques for large linear systems: A survey. Journal of Computational Physics, 182(2), 418–477.
George, A., & Liu, J. (1980). A fast implementation of the minimum degree algorithm using quotient graphs. ACM Transactions on Mathematical Software, 6(23), 337–358.
George, A. (1973). Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2), 345–363.
Czyzyk, J., Mehrotra, S., Wagner, M., & Wright, S. (1999). PCx an interior point code for linear programming. Optimization Methods and Software, 11(2), 397–430.
Karypis, G. (2015) METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, version 5.0. http://glaros.dtc.umn.edu/gkhome/metis/metis/download
Acknowledgements
The authors are thankful for the financial support of the Brazilian National Council for Technological and Scientific Development (CNPq) and UNIFACCAMP.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Rodrigues, W., Velazco, M., Oliveira, A.R.L. (2023). A Note on Matrix Reordering for Linear System Solutions by Iterative Methods in Interior Point Methods. In: Grothe, O., Nickel, S., Rebennack, S., Stein, O. (eds) Operations Research Proceedings 2022. OR 2022. Lecture Notes in Operations Research. Springer, Cham. https://doi.org/10.1007/978-3-031-24907-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-24907-5_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-24906-8
Online ISBN: 978-3-031-24907-5
eBook Packages: Business and ManagementBusiness and Management (R0)