FME relies on a pivoting rule similar to Gaussian elimination, it "eliminates"
dimensions from the combined polytope on :
Its core idea goes as follows. First, use the equality constraints and to eliminate as many coordinates from
as possible. This leaves us with a reduced polytope:
Now, consider the first coordinate . Each line of the inequality
constraint can be written as:
One of three outcomes can happen:
- : in this case, dividing by this number yields a lower
bound , with
- : then, doing the same yields an upper bound
- : in this case, the inequality is independent from
, i.e. it is already part of the projection where
has been eliminated.
By construction, where is the highest of
all lower bounds obtained by the above process, and is similarly
the lowest of all upper bounds. Therefore, the system of linear inequalities
has solutions if and only if this interval is nonempty, that is to say,
The key idea here is that the expressions of 's and 's
only depend on . To eliminate , we
- remove from and all lines for which
- add one new line for each pair (i, j) of lower and upper bounds on
corresponding to .
The result from this operation is a new polytope over , from which the elimination can be repeated until the only
remaining coordinates are and .
As can be readily seen from the combinatorics of its update rule,
Fourier-Motzkin elimination has a (doubly) exponential memory complexity.
Imbert has proposed a set of syntactic rules
to avoid considering pairs of lower-upper bounds that yield redundant
inequalities, but without lowering the worst-case complexity of the overall