Weakly redundant constraints and their impact on postoptimal analyses in LP

Suppose that in a mathematical programming problem with a smooth objective function the constraints set is formed by linear inequalities. Then, as is well known, it is possible to determine redundant constraints before the optimization procedure starts. If some of the vertices of the convex polyhedron defined by the linear constraints are degenerate, the known redundancy-determining procedures may fail. Based on the recently developed theory of degeneracy graphs (DG’s for short) a procedure is suggested how to proceed in degenerate cases. Weakly redundant constraints which cause degeneracy do have some impact on sensitivity analyses with respect to the RHS or objective function coefficients. Using again the theory of DG’s this impact is analysed. Also procedures are suggested how to perfrom sensitivity analyses when the degeneracy of the optimal vertex is not caused only by weakly redundant constraints. Small numerical examples are used for illustration.