FOURIER–MOTZKIN ELIMINATION

(Redirected from Fourier-Motzkin elimination)
'Fourier–Motzkin elimination' is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can both look for real and for integer solutions. It is computationally expensive.
Elimination (or $exists$-elimination) of variables ''V'' from a system of relations (here, linear inequalities) consists in creating another system of the same kind, but without the variables ''V'', such that both systems have the same solutions over the remaining variables.
If one eliminates all variables from a system of linear inequalities, then one obtains a system of constant inequalities, which can be trivially decided to be true or false, such that this system has solutions (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.
Let us consider a system $S$ of $n$ inequalities with $r$ variables $xi\_1$ to $xi\_r$, with $xi\_r$ the variable to eliminate. The linear inequalities in the system can be grouped into three classes, depending on the sign (positive, negative or null) of the coefficient for $xi\_r$:

★ those that are equivalent to some inequalities of the form $xi\_r\; geq\; sum\_\{k=1\}^\{r-1\}\; a\_k\; xi\_k$; let us note these as $xi\_r\; geq\; A\_i(xi\_1,\; dots,\; xi\_\{r-1\})$, for $i$ ranging from 1 to $n\_A$ where $n\_A$ is the number of such inequalities;

★ those that are equivalent to some inequalities of the form $xi\_r\; leq\; sum\_\{k=1\}^\{r-1\}\; a\_k\; xi\_k$; let us note these as $xi\_r\; leq\; B\_i(xi\_1,\; dots,\; xi\_\{r-1\})$, for $i$ ranging from 1 to $n\_B$ where $n\_B$ is the number of such inequalities;

★ those in which $xi\_r$ plays no role, grouped into a single conjunction $phi$.
The original system is thus equivalent to $max(A\_1(xi\_1,\; dots,\; xi\_\{r-1\}),\; dots,\; A\_\{n\_A\}(xi\_1,\; dots,\; xi\_\{r-1\})\; leq\; xi\_r\; leq\; min(B\_1(xi\_1,\; dots,\; xi\_\{r-1\}),\; dots,\; B\_\{n\_A\}(xi\_1,\; dots,\; xi\_\{r-1\})\; wedge\; phi$.
Elimination consists in producing a system equivalent to $exists\; xi\_r~S$. Obviously, the above formula is equivalent to $max(A\_1(xi\_1,\; dots,\; xi\_\{r-1\}),\; dots,\; A\_\{n\_A\}(xi\_1,\; dots,\; xi\_\{r-1\})\; leq\; min(B\_1(xi\_1,\; dots,\; xi\_\{r-1\}),\; dots,\; B\_\{n\_A\}(xi\_1,\; dots,\; xi\_\{r-1\})\; wedge\; phi$.
The inequality $max(A\_1(xi\_1,\; dots,\; xi\_\{r-1\}),\; dots,\; A\_\{n\_A\}(xi\_1,\; dots,\; xi\_\{r-1\})\; leq\; min(B\_1(xi\_1,\; dots,\; xi\_\{r-1\}),\; dots,\; B\_\{n\_A\}(xi\_1,\; dots,\; xi\_\{r-1\})$ is equivalent to $n\_A\; n\_B$ inequalities $A\_i(xi\_1,\; dots,\; xi\_\{r-1\})\; leq\; B\_j(xi\_1,\; dots,\; xi\_\{r-1\})$, for $1\; leq\; i\; leq\; n\_A$ and $1\; leq\; j\; leq\; n\_B$.
We have therefore transformed the original system into another system where $xi\_r$ is eliminated. Note that the output system has $(n-n\_A-n\_B)+n\_A\; n\_B$ inequalities. In particular, if $n\_A\; =\; n\_B\; =\; n/2$, then the number of output inequalities is $n^2/4$.

Contents

See also

References

See also

★ Real closed field: the cylindrical algebraic decomposition algorithm performs quantifier elimination over ''polynomial'' inequalities, not just linear

References

★ Alexander Schrijver, ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, ISBN 0-471-98232-6, pp. 155-156

★ Keβler, Christoph W., ''Parallel Fourier–Motzkin Elimination'', Universität Trier Citeseer page
----