Computational experience with a primal-dual interior point method for linear programming (Q808184)

This important paper describes the heuristics and implementation details used in the code OB1, which implements a primal-dual interior point algorithm for linear programming. The algorithm is motivated in terms of the logarithmic barrier function, and the strategy for choosing the initial point and the heuristic for decreasing the barrier parameter are described. The authors discuss the main computational engine of the code, namely, the preconditioned conjugate gradient algorithm for solving the sparse linear system of equations that arises at each iteration. The preconditioner is of the incomplete Cholesky type, but special care is needed in handling columns of the constraint matrix which destroy the sparsity of the coefficient matrix. Computational comparisons with the MINOS simplex code are given for problems in the expanded netlib test set.