Ilan Adler, Narendra Karmarkar, Mauricio G.C. Resende, and Geraldo Veiga

ORSA J. on Computing, vol. 1, pp. 84-106, 1989.

ABSTRACT

This paper describes data structures and programming techniques used in an implementation of Karmarkar's algorithm for linear programming.  Most of our discussion focuses on applying Gaussian elimination toward the solution of a sequence of sparse symmetric positive definite systems of linear equations, the main requirement in Karmarkar's algorithm.  Our approach relies on a direct factorization scheme, with an extensive symbolic factorization step performed in a preparatory stage of the linear programming algorithm. An interpretative version of Gaussian elimination makes use of the symbolic information to perform the actual numerical computations at each iteration of the algorithm.  We also discuss ordering algorithms that attempt to reduce the amount of fill-in in the LU factors, a procedure to build then linear system solved at each iteration, the use of a dense window data structure in the Gaussian elimination method, a preprocessing procedure designed to increase the sparsity of the linear programming coefficient matrix, and the special treatment of dense columns in the coefficient matrix.

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Copyright Notice