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, which 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 to obtain software implementation of practical interest. In this paper, we propose a detection technique. We demonstrate its benefits over alternative approaches. A detailed experimentation is reported.