Effects of ordering and updating techniques on the performance of the Karmarkar algorithm

This paper will report experimental results obtained with two implementations of the Karmarkar algorithm. In one implementation it is assumed that the optimum objective value is available while in the other, this assumption is dropped. The study is particularly concerned with the performance of the algorithm in conjunction with sparsity preservation techniques, namely the nested dissection ordering algorithm of Alan George and the updating algorithm for least squares of Heath. Standard test problems are solved with FORTRAN 77 codes of the algorithm as well as with the well known LP package LINDO. In addition, a numerical example is given to illustrate the algorithm and its geometric features.