On degeneracy in linear programming and related problems

Methods related to Wolfe’s recursive method for the resolution of degeneracy in linear programming are discussed, and a nonrecursive variant which works with probability one suggested. Numerical results for both nondegenerate problems and problems constructed to have degenerate optima are reported. These are obtained using a careful implementation of the projected gradient algorithm. These are compared with results obtained using a steepest descent approach which can be implemented by means of a closely related projected gradient method, and which is not affected by degeneracy in principle. However, the probem of correctly identifying degenerate active sets occurs with both algorithms. The numerical results favor the more standard projected gradient procedure which resolves the degeneracy explicitly. Extension of both methods to general polyhedral convex function minimization problems is sketched.