Computational Experience with a Preconditioner for Interior Point Methods for Linear Programming

. In this paper, we discuss efficient implementation of a new class of preconditioners for linear systems arising from interior point methods. These new preconditioners give superior performancenear the solution of a linear programming problem where the linear systems are typically highly ill-conditioned. They rely upon the computation of an LU factorization of a subset of columns of the matrix of constraints. The implementation of these new techniques require some sophistication since the subset of selected columns is not known a priori. The conjugate gradient method using this new preconditioner compares favorably with the Cholesky factorization approach. The new approach is clearly superior for large scale problems where the Cholesky factorization produces intractable fillin. Numerical experiments on several representative classes of linear programming problems are presented to demonstrate the promise of the new preconditioner. Key words. linear programming, interior-point methods,..