Ilan Adler, Narendra Karmarkar, Mauricio G.C. Resende, and Geraldo Veiga
This article originally appeared in Mathematical Programming, vol. 44, pp. 297-335, 1989. An errata correcting the description of the power series algorithm was published in Mathematical Programming, vol. 50, p. 415, 1991. The version presented here incorporates these corrections to the body of the article. In addition, we updated references to some articles published in final form after the publication of this paper.
ABSTRACT
This paper describes the implementation of power
series dual affine scaling variants of Karmarkar's algorithm for linear
programming. Based on a continuous version of Karmarkar's algorithm, two
variants resulting from first and second order approximations of the
continuous trajectory are implemented and tested. Linear programs
are expressed in an inequality form, which allows for the inexact
computation of the algorithm's direction of improvement, resulting in a
significant computational advantage. Implementation issues
particular to this family of algorithms, such as treatment of dense
columns, are discussed. The code is tested on several standard
linear programming problems and compares favorably with the simplex code
MINOS 4.0.
PostScript file of full paper
Go back
Mauricio G.C. Resende's Home PageLast modified: 28 June 2002