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

AbstractA new comprehensive implementation of a primal-dual algorithm for linear programming is described. It allows for easy handling of simple bounds on the primal variables and incorporates free variables, which have not previously been included in a primal-dual implementation. We discuss in detail a variety of computational issues concerning the primal-dual implementation and barrier methods for linear programming in general. We show that, in a certain way, Lustig's method for obtaining feasibility is equivalent to Newton's method. This demonstrates that the method is in some sense the natural way to reduce infeasibility. The role of the barrier parameter in computational practice is studied in detail. Numerical results are given for the entire expanded NETLIB test set for the basic algorithm and its variants, as well as version 5.3 of MINOS