Computing the projection in an interior point algorithm:  An experimental comparison

Mauricio G.C. Resende and Geraldo Veiga

Investigacion Operativa, vol. 3, pp. 81-92, 1993


This paper reports on a computational study comparing two implementations of the ascent direction (projection) computation in the dual affine scaling algorithm for linear programming.  The first is the direct factorization code described in Adler, Karmarkar, Resende and Veiga (1989).  The second is the preconditioned conjugate gradient code described in Resende and Veiga (1990).  The codes are identical with the exception of the ascent direction computation.  We show that for a class of minimum cost network flow problems the conjugate gradient approach leads to substantially faster solution times.


PostScript file of full paper

Go back

Mauricio G.C. Resende's Home Page


Last modified: 23 November 1995

Copyright Notice