I have a set of $m$ linear inequalities in $R^n$, of the form $$ A x \leq b $$ These are automatically generated from the specification of my problem. Many of them could be removed because they are implied by the others.
I would like to find the minimal set of inequalities, $$ A' x \leq b' $$ such that a solution to the first problem is also a solution to the second, and vice versa.
One way to do this is to apply Fourier-Motzkin Elimination: I pick one inequality, $a_1 x \leq b_1$, I negate it as $-a_1 x < -b'$, I add it back to the system, and apply FME: if the result is an empty space, then the original inequality can be safely eliminated. Unfortunately, FME is a complex algorithm, and in the worst case it must be applied $m$ times.
Another possibility is to use linear programming: again, I remove one inequality $a_1 x \leq b$, and I call the remaining set of inequalities $A'' x \leq b''$. Then, I find an optimum for the problem $$ \max \;\; a_1 x \\ A'' x \leq b'' $$ using e.g. simplex, and finally I compare the result with $b$: if $a_1 x' < b$ then the inequality can be safely removed, otherwise it must be kept. Again, this has the same complexity of the simplex applied $m$ times (and $m$ is potentially very large).
Anyone knows a better algorithm?