A NEW DEGENERACY METHOD AND STEEPEST-EDGE-BASED CONDITIONING FOR LP

A new recursive method for resolving degeneracy in simplex-like method s for linear programming (LP) is described. The method provides a guar antee of termination, even in the presence of round-off errors, and is readily implemented. In contrast to a previous method of the author, this method works throughout in the primal space. One consequence is t hat the steepest-edge criterion can be used on all iterations and at a ll levels of recursion. It is also shown that the associated steepest- edge coefficients provide information from which the expected conditio n of the current LP basis can be calculated cheaply. This provides a m ore accurate indication of the actual condition of a system than is ob tained from norm-based condition numbers. This idea also enables the c ondition of null space matrices to be estimated.