Fourier–Motzkin Elimination

1. The feasibility problem

A related question to the linear program optimization problems we’ve been solving is the existence question:

given A and b, is the set {x ∈ R^n : Ax ≤ b} nonempty? In other words, does there exist a feasible solution to a linear program?

We already have methods to solve this problem. Right now, one reasonable approach is to use the dual simplex method:

• If necessary, put the constraints into equational form.
• Find a basic solution (not necessarily a feasible one) by row reduction.
• Invent an objective function that will give us a dual feasible tableau.
• Use the dual simplex method to try to make the tableau primal feasible as well.

This subproblem captures most of the important features of linear programming as well: it’s not significantly easier than an optimization problem.

For example, we could use the feasibility problem to answer questions like: “Given a linear program min{c^Tx : Ax ≥ b, x ≥ 0}, does the optimal solution have objective value at least z_0?”

To do so, just add c^Tx ≥ z_0 as a constraint and ask if any point x ∈ R^n satisfies all of the constraints including this one.

2. Fourier–Motzkin elimination

There is another algorithm for solving the feasibility problem, which is very different from the simplex method. Here, “very different” is kind of like “worse”, for large problems. But this algorithm, called Fourier–Motzkin elimination, is still occasionally interesting. It’s simpler, so it’s easier to prove things about. And for small problems, it might not even be that bad to use.

2.1 The algorithm

The idea of the algorithm is just this: first, we find a procedure to reduce an n-variable problem to an equivalent (n − 1)-variable problem. (Equivalent means that one system of inequalities has a feasible solution if and only if the other one does.) Then, repeat this procedure, eliminating variables one at a time.

Eventually, we’ll be left with a 1-variable problem, and these are easy to solve: just check if there are any numbers between the greatest lower bound and the least upper bound. We will even be able to trace back our steps, using a solution to the 1-variable problem to find solutions to the 2-variable, 3-variable, and eventually the original n-variable problem.

So how do we eliminate a variable? Well, let’s suppose we have variables x1, x2, . . . , xn, and we want to eliminate xn.

Our first step is to solve for xn. For each inequality such as:

we will get one of the two inequalities

depending on whether an > 0 or an < 0. (If an = 0, we’ll leave the inequality alone, since it doesn’t involve xn to begin with.)

We’ll end up with a collection of lower and upper bounds:

Here, each Li and Uj is an expression in the n − 1 variables x1, x2, . . . , xn−1. It’s possible to choose a value of xn that satisfies all these bounds if and only if

because there’s something in between all the lower bounds and all the upper bounds. Unfortunately, we can’t just write down this single equation, because the lower and upper bounds are all in terms of unknown values x1, . . . , xn−1, so we can’t tell which ones are larger or smaller. So we compromize by writing down k · m inequalities:

If an xn exists that satisfies all the constraints, then for every i and j, Li ≤ xm ≤ Uj , so all of these inequalities hold. Conversely, if all of these inequalities hold, then the max-min inequality holds as well, and we can choose xn between max{L1, . . . , Lk} and min{U1, . . . , Um}.

This results in our new system in only n − 1 variables. It consist of the k · m inequalities above, plus any of the original inequalities which didn’t involve xn in them to begin with.

2.2 Example

Suppose that we have a system of inequalities

We begin by eliminating y. First, we solve for y in each inequality

Next, we pair up the lower bounds and upper bounds. This gives us four inequalities on x, together with a fifth one which is just x ≥ 0:

These inequalities can all be simplified into lower bounds or upper bounds on x:

In this case, they all happen to be lower bounds, so we know that they can be satisfied: for instance, setting x = 7 works. Then our lower and upper bounds on y become constants: we have y ≤ 6, y ≥ 4, y ≤ 4, and y ≥ 0. So we can set y = 4, and find a feasible solution.

2.3 Complexity

The downside of this method is that, in typical cases, the number of inequalities grows very quickly. For instance, here’s one possible way that Fourier–Motzkin elimination can go:

8 inequalities in x1, x2, x3, x4

=⇒ 4 lower and 4 upper bounds on x4

=⇒ 4 × 4 = 16 inequalities in x1, x2, x3

=⇒ 8 lower and 8 upper bounds on x3

=⇒ 8 × 8 = 64 inequalities in x1, x2

=⇒ 32 lower and 32 upper bounds on x2

=⇒ 32 × 32 = 1024 inequalities in x1

The above is worst-case behavior: the types of bounds are split exactly in half every time. But we expect roughly half of each type of bound, so this is not too far off from typical behavior, either

If we started with just 8 inequalities in n variables, then this pattern would continue to give us 2^(2^k+2) inequalities in n − k variables all the way up until we get 2^(2^(n−1)+2) inequalities in 1 variable on the very last step. This is worse than exponential: this is doubly exponential.

3 Farkas’s lemma

Nevertheless, Fourier–Motzkin elimination is useful. For one thing, we can get the following result from it very quickly:

Theorem 3.1 (Farkas’s lemma). For any system of inequalities Ax ≤ b, either there exists a feasible solution x, or we can take a linear combination of the inequalities to derive a contradiction: there exists a vector u ≥ 0 such that u TA = 0 T but u Tb < 0.

(The existence of u is the same as being able to derive a contradiction, because, left-multiplying Ax ≤ b by u^T, we deduce 0^Tx < 0, or 0 < 0.)

Proof. Throughout Fourier–Motzkin elimination, all the inequalities we get have the form v^TAx ≤ v^Tb for some v ≥ 0.

To see this, note that we can do everything in the algorithm using only two kinds of steps:

• Instead of solving for xn, just divide through by |an|, the absolute value of the coefficient. The new inequality is a nonnegative multiple of the old one, and has xn in it with a coefficient of 1 or −1.
• Instead of combining a lower bound and an upper bound, just add together an inequality with +xn and an inequality with −xn. The new inequality eliminates xn, and is definitely a nonnegative linear combination of preceding inequalities.

If Fourier–Motzkin elimination fails to find a solution, then we get a lower bound on x1 and an upper bound on x1 that contradict each other: linear combinations of the original inequalities that look like x1 ≤ U and −x1 ≤ −L with L > U. Adding these together, we get 0 ≤ U − L, which is exactly the kind of contradiction we were looking for.

Farkas’s lemma is important because it is the equivalent of strong duality for the feasibility problem: the system “u^TA = 0^T and u^Tb < 0 and u ≥ 0” is a dual feasibility problem to the original. We could have used Farkas’s lemma to prove strong duality for linear programs, without relying on the correctness of the simplex method to get there.