Numerical experiments with the symmetric affine scaling algorithm on degenerate linear programming problema

Abstract

In this paper we report numerical results on the symmetric afline scaling algorithm applied to degenerate linear programming problems. The performance is measured in terms of the number of iterations needed to reach a prefixed level of tolerance. We have found that the number of iterations increases with the number of primal variables and, for most problems, slightly decreases with the increase of degeneracy. Problems are randomly generated, with a prescribed degree of degeneracy

Keywords:

• Linear programming
• Degenerate problems
• Affine scaling algorithm

‡This work has been supported by Universidad de Chile, under contract DTI-E-3456-9211 and Fundaci6n Andes.

‡This work has been supported by Universidad de Chile, under contract DTI-E-3456-9211 and Fundaci6n Andes.

Notes

‡This work has been supported by Universidad de Chile, under contract DTI-E-3456-9211 and Fundaci6n Andes.