Fourier-Motzkin elimination is one of those methods that gets a page and a half in the linear programming textbooks, right before the simplex method shows up and steals the whole show. I was first introduced to it while working as an OR analyst at Cargill, and my honest first reaction was: nice, but why would I ever use this? It took me years (and one very stubborn model) to change my mind. This post is the explanation I wish someone had given me back then: what the method actually does, how the mechanics work, and a small worked example showing a model before and after the elimination.
What Fourier-Motzkin elimination actually does
You already know Gaussian elimination: take a system of linear equations, eliminate variables one at a time, and either solve the system or discover it has no solution. Fourier-Motzkin elimination is the same idea for linear inequalities. You pick a variable, you eliminate it, and you are left with a new system of inequalities that involves one variable fewer — and that new system has a solution exactly when the original one does.
The geometric picture is the one that made it click for me. A system of linear inequalities defines a polyhedron. Eliminating a variable is the same as projecting that polyhedron onto the remaining variables — like shining a light from above and looking at the shadow the solid casts on the floor. The shadow is itself a polyhedron, and Fourier-Motzkin hands you its inequalities explicitly. That is something the simplex method never gives you: simplex finds a point, Fourier-Motzkin gives you the whole projected region.
The method is old. Joseph Fourier (the series guy, yes) described it in the 1820s, and Theodore Motzkin rediscovered it in the 1930s, decades before linear programming was even a field. There’s a decent summary on Wikipedia if you want the formal treatment.
The mechanics: pair every lower bound with every upper bound
Say you want to eliminate a variable y. First, rewrite every constraint so y is alone on one side. Each constraint becomes one of three things: an upper bound on y (something like y ≤ expression in the other variables), a lower bound on y, or a constraint that doesn’t mention y at all.
Now the key step. A value of y exists if and only if every lower bound is below every upper bound. So you write down one new inequality for every pair of a lower bound with an upper bound — lower ≤ upper — keep the constraints that never mentioned y, and throw everything else away. The variable is gone, and the new system is feasible exactly when the old one was.
That “every pair” is also the method’s curse. If a variable shows up in 10 lower bounds and 10 upper bounds, eliminating it turns 20 constraints into 100. Do that a few times in a row and the constraint count explodes — which is exactly why nobody solves industrial LPs this way, and why the textbooks move on to simplex so quickly. Fair enough. But “bad general-purpose solver” is not the same as “useless,” and that’s the part the textbooks undersell.
Why a practitioner should still care
In theory, Fourier-Motzkin is the workhorse behind some beautiful results — you can use it to prove Farkas’ lemma and LP duality with nothing fancier than high school algebra. In practice, the reason I keep it in the toolbox is more mundane: it lets you get rid of variables you don’t actually care about.
Real models are full of auxiliary variables — assignments, flows, intermediate quantities — that exist only to make the formulation writable. Sometimes what you really want is the constraint set expressed purely in the decision variables that matter to you. Fourier-Motzkin is the systematic way to get there: eliminate the nuisance variables, and the projected constraints that come out are the exact conditions your remaining variables must satisfy. Done by hand on a structured model, the blow-up is often very manageable, and the constraints you get frequently have a meaning you can read off in plain language (I have a real example of this involving, of all things, baseball — but that’s a story for another post).
A small example: before and after
Let’s run the method end to end on a tiny LP. Here is the model before elimination:
maximize z = x + y
subject to x + 2y ≤ 6
2x + y ≤ 6
x ≥ 0, y ≥ 0
where x, y are the (continuous) decision variables.
One preliminary trick: to handle the objective with the same machinery, treat it as a constraint. We want the largest z compatible with the system, so add z ≤ x + y and carry z along as if it were another variable.
Eliminate y. Rewrite every constraint as a bound on y:
y ≤ (6 − x) / 2 (upper)
y ≤ 6 − 2x (upper)
y ≥ 0 (lower)
y ≥ z − x (lower, from the objective constraint)
Two lowers times two uppers = four new constraints. Pair them up (lower ≤ upper) and simplify:
0 ≤ (6 − x) / 2 → x ≤ 6
0 ≤ 6 − 2x → x ≤ 3
z − x ≤ (6 − x) / 2 → x ≥ 2z − 6
z − x ≤ 6 − 2x → x ≤ 6 − z
So after eliminating y the model reads:
maximize z
subject to 0 ≤ x ≤ 3, x ≤ 6
2z − 6 ≤ x ≤ 6 − z
where x is the only decision variable left (plus z tracking the objective).
Same feasible shadow, one variable fewer. And nothing stops us from doing it again. Eliminate x: the lower bounds are {0, 2z − 6} and the upper bounds are {3, 6, 6 − z}. Pairing them all up, the pairs that actually say something about z are:
0 ≤ 6 − z → z ≤ 6
2z − 6 ≤ 3 → z ≤ 4.5
2z − 6 ≤ 6 − z → z ≤ 4
Every variable is gone and the tightest surviving bound is z ≤ 4. That’s not just a bound — it is the optimum. We solved the LP with nothing but algebra: max z = 4. Substitute back and you recover the solution: z = 4 forces x = 2, which forces y = 2. Check it against the original constraints: 2 + 4 = 6 ✓ and 4 + 2 = 6 ✓, both tight, exactly where you’d expect the optimum of a 2-variable LP to sit.
Four constraints became four, then those became three — no explosion here, because the example is tiny. On a real model you have to pick your elimination order carefully or the constraint count will bury you (ask me how I know). But when the structure is right, this 190-year-old method turns a formulation you can’t use into one you can. Next time: the day it earned its keep on a problem nobody would call industrial.
Things that I use, like, and am affiliated with:
Mint Mobile offers great cell phone service for $15 flat, get $15 off using the link. Get discounted phones with service activation and no contract.
I never spend money before I check Mr Rebates or Rakuten to get cashbacks, rebates, discounts, coupons or cheaper gift cards.