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.

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 $S$ of $n$ inequalities with $r$ variables $x_1$ to $x_r$ , with $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 $x_r$ .

those inequalities that are of the form $x_r \geq b_i-\sum_{k=1}^{r-1} a_{ik} x_k$ ; denote these by $x_r \geq A_j(x_1, \dots, x_{r-1})$ , for $j$ ranging from 1 to $n_A$ where $n_A$ is the number of such inequalities;
those inequalities that are of the form $x_r \leq b_i-\sum_{k=1}^{r-1} a_{ik} x_k$ ; denote these by $x_r \leq B_j(x_1, \dots, x_{r-1})$ , for $j$ ranging from 1 to $n_B$ where $n_B$ is the number of such inequalities;
those inequalities in which $x_r$ plays no role, grouped into a single conjunction $\phi$ .

The original system is thus equivalent to

\max(A_1(x_1, \dots, x_{r-1}), \dots, A_{n_A}(x_1, \dots, x_{r-1})) \leq x_r \leq \min(B_1(x_1, \dots, x_{r-1}), \dots, B_{n_B}(x_1, \dots, x_{r-1})) \wedge \phi

Elimination consists in producing a system equivalent to $\exists x_r~S$ . Obviously, this formula is equivalent to

\max(A_1(x_1, \dots, x_{r-1}), \dots, A_{n_A}(x_1, \dots, x_{r-1})) \leq \min(B_1(x_1, \dots, x_{r-1}), \dots, B_{n_B}(x_1, \dots, x_{r-1})) \wedge \phi

The inequality

\max(A_1(x_1, \dots, x_{r-1}), \dots, A_{n_A}(x_1, \dots, x_{r-1})) \leq \min(B_1(x_1, \dots, x_{r-1}), \dots, B_{n_B}(x_1, \dots, x_{r-1}))

is equivalent to $n_A n_B$ inequalities $A_i(x_1, \dots, x_{r-1}) \leq B_j(x_1, \dots, x_{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 $x_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$ .

Complexity

Running an elimination step over $n$ inequalities can result in at most $n^2/4$ inequalities in the output, thus running $d$ successive steps can result in at most $4(n/4)^{2^d}$ , a double exponential complexity. This is due to the algorithm producing many unnecessary constraints (constraints that are implied by other constraints). The number of necessary constraints grows as a single exponential.^[1] Unnecessary constraints may be detected using linear programming.

References

↑ David Monniaux, Quantifier elimination by lazy model enumeration, Computer aided verification (CAV) 2010.

Fourier, Joseph (1827). "Histoire de l'Académie, partie mathématique (1824)". Mémoires de l'Académie des sciences de l'Institut de France 7. Gauthier-Villars.
Schrijver, Alexander (1998). Theory of Linear and Integer Programming. John Wiley & sons. pp. 155–156. ISBN 0-471-98232-6.
Keßler, Christoph W. "Parallel Fourier–Motzkin Elimination". Universität Trier. CiteSeerX: 10.1.1.54.657. Missing or empty |url= (help)
Williams, H. P. (1986). "Fourier's Method of Linear Programming and its Dual". American Mathematical Monthly 93 (9): 681–695. doi:10.2307/2322281.

External links

Lectures on Convex Sets, notes by Niels Lauritzen, at Aarhus University, March 2010.

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear: Methods calling …

… functions

… and gradients

Convergence	Trust region Wolfe conditions

Quasi–Newton	BFGS and L-BFGS DFP Symmetric rank-one (SR1)

Other methods	Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient

… and Hessians

Newton's method

The graph of a strictly concave quadratic function is shown in blue, with its unique maximum shown as a red dot. Below the graph appears the contours of the function: The level sets are nested ellipses.

Constrained nonlinear

General	Barrier methods Penalty methods

Differentiable	Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization

Convex
minimization

Linear and
quadratic

Interior point	Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar

Basis-Exchange	Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial

Paradigms

Graph
algorithms

Minimum spanning tree	Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal

Network flows

Dinic
Edmonds–Karp
Ford–Fulkerson
Push-relabel maximum flow

Metaheuristics

Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search

Categories
- Algorithms and methods
- Heuristics
Software

Fourier–Motzkin elimination

Elimination

Complexity

See also

References

External links