This problem is essentially equivalent to the redundancy removal from point sets given in 2.20.
Although one can transform one to the other, let us describe
a direct method. Let
be a given system of
-inequalities in
-variables
.
We want to test whether the subsystem of first
inequalities
implies the last inequality
. If so,
the inequality
is redundant
and can be removed from the system.
A linear programming (LP)
formulation of this checking is rather straightforward:
By successively solving this LP for each untested inequality against the remaining, one would finally obtain a equivalent non-redundant system.
As we discussed in 2.20, one might
be able to remove many redundant inequalities by using
the same technique in dual form. Let be the
given system with high redundancy. The first step is to
select a small subsystem
of non-redundant inequalities from
the original system. Typically such a system contains
only
inequalities for some small
(say
or
).
The second step is to compute all extreme points
of
. (Here we assume that
is bounded,
but one can generalize the technique for the unbounded case.)
This is known as the vertex enumeration computation, 2.12.
Clearly
contains the feasible region
.
The final step is to test whether each original inequality
is satisfied by all extreme points and rays.
If so, the inequality is redundant for the subsystem and
thus redundant for the original system.