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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Weakly redundant constraints and their impact on postoptimal analyses in LP
scientific article

    Statements

    Weakly redundant constraints and their impact on postoptimal analyses in LP (English)
    0 references
    0 references
    16 January 1993
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    degeneracy graphs
    0 references
    sensitivity analysis
    0 references
    degeneracy
    0 references
    0 references