An Implementation of a Revised Karmarkar's Method

We will show a variant of the Karmarkar's algorithm for LPs with sparse matrices. We deal with the standard form LP. Starting from an initial interior point, one interation of our method consists of choice of a basis, factorization of the basis, optimality test, reduced gradient, conjugate gradient method and determination of the next point of iterate. A combination of the reduced gradient and the conjugate gradient method is used for generating the steepest descent direction of the transformed objective function. Bases which are maintained and updated throughout the iterations are effectively utilized. As a basis, we choose the linearly independent columns of the coefficient matrix corresponding to the decreasing order of the variables. The basis is then factorized in the LU-form which is used in the computations throughout the iteration. Preliminary numerical experiments will be reported. Emphasis is laid on the implementational issues of the sparse basis.departmental bulletin pape