FME relies on a pivoting rule similar to Gaussian elimination, it "eliminates"
x dimensions from the combined polytope on [xy]:
Its core idea goes as follows. First, use the equality constraints Cx=d and y=Ex+f to eliminate as many coordinates xi from
x as possible. This leaves us with a reduced polytope:
Now, consider the first coordinate x0. Each line of the inequality
constraint can be written as:
One of three outcomes can happen:
- Ai,0′<0: in this case, dividing by this number yields a lower
bound x0≥li, with
- Ai,0′>0: then, doing the same yields an upper bound
- Ai,0′=0: in this case, the inequality is independent from
x0, i.e. it is already part of the projection where x0
has been eliminated.
By construction, x0∈[l∗,u∗] where l∗ is the highest of
all lower bounds obtained by the above process, and u∗ 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 li's and uj's
only depend on x1,…,xk,y0,y1. To eliminate x0, we
- remove from A′ and b′ all lines i for which
- add one new line for each pair (i, j) of lower and upper bounds on
x0 corresponding to li−uj≤0.
The result from this operation is a new polytope over [x1⋯xky0y1], from which the elimination can be repeated until the only
remaining coordinates are y0 and y1.
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