Efficient detection of redundancies in systems of linear inequalities

Fourier-Motzkin elimination is a fundamental operation in polyhedral geometry. It can be performed by several equivalent procedures, and can be regarded as an adaptation of Gaussian elimination to systems of linear inequalities. These procedures tend to generate large numbers of redundant inequalities. Efficiently detecting these redundancies is essential for obtaining software implementation of practical interest. In this paper, we propose a novel detection technique. We demonstrate its benefits over alternative approaches. A detailed experimentation is reported.