|
In this paper a method for the
identification of redundant constraints
in a finite set of linear inequalities
in the n-dimensional Euclidian Space
is presented. The identification
is based on the minimization of
the distance of the hyperplane of
a restriction from the polyhedron
of feasible solutions of the set
of inequalities. The minimization
problem is formulated by a linear
programming model on the given inequalities
set, which is designed from Fase
I method of the Simplex algorithm.
By means of this minimization, the
redundant condition of a restriction
and of those restrictions adjoining
vertexes visited by the Simplex
algorithm are determined by applying
in each vertex a criterion called
raw criterion. The proposed method
is compared to two methods based
on the convex hull of the gradients
of the linear inequalities: the
first method identifies the redundant
condition of just one restriction
based on convex combinations; the
second identifies redundancies based
on the construction of the convex
hull of the complete set of constraints,
whose complexity is exponential.
Our method has advantage over the
first method because it identifies
also a set of constraints and reduces
the problem dimension by one each
time a redundant constraint is identified
and suppressed. Our method is superior
to the second method because its
complexity is comparable with that
of the Simplex algorithm. The validity
and computational efficiency of
the method presented in this paper
for redundancy identification are
described using two-dimension instances.
|