Identifying Redundant Constraints and Implicit Equalities in Systems of Linear Constraints

Abstract

Redundant constraints are constraints that can be omitted from a system of linear constraints without changing the feasible region. Implicit equalities are inequality constraints that can be replaced by equalities without changing the feasible region. We prove some theorems concerning the identification of both kinds of constraints. Based on these theorems two methods are developed that allow identification of all redundant constraints and all implicit equalities. Computational experience on small problems indicates a behavior at least competitive with other methods in this field.