Implementation of a Dual Affine Interior Point Algorithm for Linear Programming

The dual affine interior point method is extended to handle variables with simple upper bounds as well as free variables. During execution, variables which appear to be going to zero are fixed at zero, and rows with slack variables bounded away from zero are removed. A variant of the big-M artificial variable method to attain feasibility is derived. The simplex method is used to recover an optimal basis upon completion of the algorithm, and the effects of scaling are discussed. Computational experience on a variety of problems is presented.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.