    Next: Is there any efficient Up: Convex Polyhedron Previous: How can one remove   Contents

## Is there any efficient algorithm to remove redundant inequalities from a system of linear inequalities

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: (6)

Then the inequality is redundant if and only if the optimal value is less than or equal to .

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.    Next: Is there any efficient Up: Convex Polyhedron Previous: How can one remove   Contents
Komei Fukuda 2004-08-26