Fourier–Motzkin elimination

Fourier–Motzkin elimination, also known as the FME method, is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can output real solutions.

The algorithm is named after Joseph Fourier and Theodore Motzkin.

The elimination of a set of variables, say V, from a system of relations (here linear inequalities) refers to the creation of another system of the same sort, but without the variables in V, such that both systems have the same solutions over the remaining variables.

If all variables are eliminated from a system of linear inequalities, then one obtains a system of constant inequalities. It is then trivial to decide whether the resulting system is true or false. It is true if and only if the original system has solutions. As a consequence, elimination of all variables can be used to detect whether a system of inequalities has solutions or not.

Consider a system ${\displaystyle S}$ of ${\displaystyle n}$ inequalities with ${\displaystyle r}$ variables ${\displaystyle x_{1}}$ to ${\displaystyle x_{r}}$, with ${\displaystyle x_{r}}$ the variable to be eliminated. The linear inequalities in the system can be grouped into three classes depending on the sign (positive, negative or null) of the coefficient for ${\displaystyle x_{r}}$.

...
Wikipedia