Files
Abstract
In this paper the concept of redundancy in systems of linear inequalities is established from the existence of the minimal inequality representation of a system of linear constraints. It is shown that absence of redundancy is a necessary and sufficient condition for having a minimal inequality representation of the system; then a minimal inequality representation can be obtained by deleting redundant constraints. Furthermore a general method to determine redundancy is developed; this method is based on the simplex method and is greatly inspired by Gal [2]. A number of known methods can be shown to be simplified variants of this method. Finally the equivalence, in terms of complexity theory, of the problem of determining redundancy and the general linear programming problem, is proved. From this a class of problems is indicated, for which it may be fruitful to determine redundancy.