Weakly redundant constraints and their impact on postoptimal analyses in LP (Q1199513)

In mathematical programming problems it is sometimes reasonable to reduce the number of constraints from a feasible set by determining and then omitting the redundant ones. Most of the methods to determine redundant constraints for linear programming problems are based on some kind of pivoting algorithms, but if some vertices of a feasible set are degenerate, these methods may either fail or become inefficient. In the article a procedure is proposed how to proceed in degenerate cases. The procedure is based on the theory of degeneracy graphs (DG's). The theory of DG's is used also for finding the overall critical interval for sensitivity analysis with respect to the right-hand-sides or objective function coefficients in the case of degeneracy. Small numerical examples are used to illustrate a new procedure and finding the overall critical intervals.