next up previous contents
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 $ A x \le b, s^T x \le t$ be a given system of $ m+1$-inequalities in $ d$-variables $ x=(x_1,x_2,\ldots,x_d)^T$. We want to test whether the subsystem of first $ m$ inequalities $ A x \le b$ implies the last inequality $ s^T x \le t$. If so, the inequality $ s^T x \le t$ is redundant and can be removed from the system. A linear programming (LP) formulation of this checking is rather straightforward:

\begin{align*}\begin{array}{lll} f^* = &\text{maximize} & s^T x\\ &\text{subject to} & A x \le b\\ & & s^T x \le t+1. \end{array}\end{align*} (6)

Then the inequality $ s^T x \le t$ is redundant if and only if the optimal value $ f^*$ is less than or equal to $ t$.

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 $ A x \le b$ be the given system with high redundancy. The first step is to select a small subsystem $ A' x \le b'$ of non-redundant inequalities from the original system. Typically such a system contains only $ d+k$ inequalities for some small $ k$ (say $ 2$ or $ 3$). The second step is to compute all extreme points of $ P'=\{x : A' x \le b'\}$. (Here we assume that $ P'$ is bounded, but one can generalize the technique for the unbounded case.) This is known as the vertex enumeration computation, 2.12. Clearly $ P'$ contains the feasible region $ P=\{ x : A x \le b \}$. 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 up previous contents
Next: Is there any efficient Up: Convex Polyhedron Previous: How can one remove   Contents
Komei Fukuda 2004-08-26