Techniques that strive to combat the influence of degeneracy in linear programming problems

Degeneracy can cause enormous problems when solving large scale linear programming problems. This is not only because there is a possibility that the problem can cycle, but also because a large number of iterations can be executed that do not improve the objective. In this article a procedure which utilizes derived reduced costs is discussed. The derived reduced cost of a non-basic variable is defined in such a way that it makes the introduction of the non-basic variable into the basis unattractive if such a decision fails to improve the objective. The procedure deliberately strives to combat degeneracy using derived reduced costs, but it also utilizes the advantageous properties of the classical gradient methods. Results achieved with the method are also reported.