Numerical aspects in developing LP softwares, LPAKO and LPABO

摘要

We have developed two public domain linear programming programs for several years, LPAKO and LPABO, which can solve large-scale sparse LP problems stably and fast. In this paper, several important numerical aspects which were considered in developing LPAKO and LPABO are presented. Common issues are scaling, tolerances and presolving. For the LPAKO, LU factorization and pivoting rule are important aspects. In case of LPABO, Cholesky factorization, ordering and dense column handling are important. In the end of this paper, several issues to be considered in the future development are proposed.