A PRIMAL NULL-SPACE AFFINE-SCALING METHOD

This article develops an affine-scaling method for linear programming in standard primal form. Its descent search directions are formulated in terms of the null-space of the linear programming matrix, which, in turn, is defined by a suitable basis matrix. We describe some basic p roperties of the method and an experimental implementation that employ s a periodic basis change strategy in conjunction with inexact computa tion of the search direction by an iterative method, specifically, the conjugate-gradient method with diagonal preconditioning. The results of a numerical study on a number of nontrivial problems representative of problems that arise in practice are reported and discussed. A key advantage of the primal null-space affine-scaling method is its compat ibility with the primal simplex method. This is considered in the conc luding section, along with implications for the development of a more practical implementation.