Uniform saturation in linear inequality systems

Abstract

Redundant constraints in linear inequality systems can be characterized as those inequalities that can be removed from an arbitrary linear optimization problem posed on its solution set without modifying its value and its optimal set. A constraint is saturated in a given linear optimization problem when it is binding at the optimal set. Saturation is a property related with the preservation of the value and the optimal set under the elimination of the given constraint, phenomena which can be seen as weaker forms of excess information in linear optimization problems. We say that an inequality of a given linear inequality system is uniformly saturated when it is saturated for any solvable linear optimization problem posed on its solution set. This paper characterizes the uniform saturated inequalities and other related classes of inequalities.