Implementation and computational results for the hierarchical algorithm for making sparse matrices sparser. If A is the (sparse) coefficient matrix of linear-equality constraints, for what nonsingular T is A = TA as sparse as possible, and how can it be efficiently computed? An efficient algorithm for this Sparsity Problem (SP) would be a valuable preprocessor for linearly constrained optimization problems. In a companion paper we developed a two-pass approach to solve SP called the Hierarchical Algorithm. In this paper we report on how we implemented the Hierarchical Algorithm into a code called HASP, and our computational experience in testing HASP on the NETLIB linear-programming problems. We found that HASP substantially outperformed a previous code for SP and that it produced a net savings in optimization time on the NETLIB problems. The results allow us to give guidelines for its use in practice.
Keywords for this software
References in zbMATH (referenced in 4 articles , 1 standard article )
Showing results 1 to 4 of 4.
- Achterberg, Tobias; Bixby, Robert E.; Gu, Zonghao; Rothberg, Edward; Weninger, Dieter: Presolve reductions in mixed integer programming (2020)
- Gemander, Patrick; Chen, Wei-Kun; Weninger, Dieter; Gottwald, Leona; Gleixner, Ambros; Martin, Alexander: Two-row and two-column mixed-integer presolve using hashing-based pairing methods (2020)
- Chang, S. Frank; McCormick, S. Thomas: Implementation and computational results for the hierarchical algorithm for making sparse matrices sparser (1993)
- Chang, S. Frank; McCormick, S. Thomas: A hierarchical algorithm for making sparse matrices sparser (1992)