Redundancy in Interval Linear Systems

In a system of linear equations and inequalities, one constraint is redundant if it can be dropped from the system without affecting the solution set. Redundancy can be effectively checked by linear programming. However, if the coefficients are uncertain, the problem becomes more cumbersome. In this paper, we assume that the coefficients come from some given compact intervals and no other information is given. We discuss two concepts of redundancy in this interval case, the weak and the strong redundancy. This former refers to redundancy for at least one realization of interval coefficients, while the latter means redundancy for every realization. We characterize both kinds of redundancies for various types of linear systems; in some cases the problem is polynomial, but certain cases are computationally intractable. As an open problem, we leave weak redundancy of equations. Herein, a characterization is known only for certain special cases, but for a general case a complete characterization is still unknown.