zbMATH — the first resource for mathematics

Implementation of a dual affine interior point algorithm for linear programming. (English) Zbl 0752.90046
Summary: 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 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.

90C05 Linear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDF BibTeX Cite
Full Text: DOI