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 who proposed the method in 1826 and Theodore Motzkin who re-discovered it in 1936.
Elimination
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 of inequalities with variables to , with 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 . those inequalities that are of the form ; denote these by , for ranging from 1 to where is the number of such inequalities; those inequalities that are of the form ; denote these by , for ranging from 1 to where is the number of such inequalities; those inequalities in which plays no role, grouped into a single conjunction .
The original system is thus equivalent to
.
Elimination consists in producing a system equivalent to . Obviously, this formula is equivalent to .
The inequality
is equivalent to inequalities , for and .
We have therefore transformed the original system into another system where is eliminated. Note that the output system has inequalities. In particular, if , then the number of output inequalities is .
Example
Consider the following system of inequalities:
To eliminate x, we can write the inequalities in terms of x:
We have two inequalities with "≤" and two with "≥"; the system has a solution if the right-hand side of each "≤" inequality is at least the right-hand side of each "≥" inequality. We have 2*2 such combinations:
We now have a new system of inequalities, with one fewer variable.
Complexity
Running an elimination step over inequalities can result in at most inequalities in the output, thus naively running successive steps can result in at most , a double exponential complexity. This is due to the algorithm producing many unnecessary constraints (constraints that are implied by other constraints). Unnecessary constraints can be detected using linear programming. It follows from McMullen's upper bound theorem that the number of necessary constraints grows as a single exponential. A single exponential implementation of Fourier-Motzkin elimination and complexity estimates are given in.
Imbert's acceleration theorems
Two "acceleration" theorems due to Imbert permit the elimination of redundant inequalities based solely on syntactic properties of the formula derivation tree, thus curtailing the need to solve linear programs or compute matrix ranks.
Define the history of an inequality as the set of indexes of inequalities from the initial system used to produce . Thus, for inequalities of the initial system. When adding a new inequality (by eliminating ), the new history is constructed as .
Suppose that the variables have been officially eliminated. Each inequality partitions the set into : , the set of effectively eliminated variables, i.e. on purpose. A variable is in the set as soon as at least one inequality in the history of results from the elimination of . , the set of implicitly eliminated variables, i.e. by accident. A variable is implicitly eliminated when it appears in at least one inequality of , but appears neither in inequality nor in , all remaining variables.
A non-redundant inequality has the property that its history is minimal.
Theorem (Imbert's first acceleration theorem). If the history of an inequality is minimal, then .
An inequality that does not satisfy these bounds is necessarily redundant, and can be removed from the system without changing its solution set.
The second acceleration theorem detects minimal history sets:
Theorem (Imbert's second acceleration theorem). If the inequality is such that , then is minimal.