Let’s start with an analogy.
Equality systems : Gaussian elimination :: Inequality systems : ???
According to Kipp Martin, the answer is Fourier-Motzkin Elimination (FME) which allows one to project out variables from a system of linear inequalities. These slides from Thomas Rothvoss nicely illustrate what it means to project out (or eliminate) the variable .
Note: I don’t particularly like how Gaussian elimination is described (via row operations on a tableau, much like how the simplex method is often described). The intuition is lacking. Instead, everything I describe in this post will work on the (in)equalities themselves.
Eliminating variables in equality systems
Start with the linear equality system
Proceed by isolating the variable in each equation that contains to get
We can eliminate variable by setting all “definitions” of equal to each other (and leaving other equations as is)
By isolating and then eliminating variable , we get . Back-substitution gives
So the only feasible solution is . Observe that each time a variable is eliminated, one equality is also removed.
Eliminating variables in inequality systems
Suppose we started with the inequality system
Isolating (where possible) gives
Matching each of the lower bounds on with each of its upper bounds (and leaving other inequalities as is), we obtain
Eliminating from the string of inequalities gives
Applying the same procedure to eliminate , we are left with
This is the projection of the original feasible set onto the space of the variable. That is,
- for any there exist values for and for which the original system is satisfied, and
- any point that is feasible for the original system satisfies .
Consequences of Fourier-Motzkin Elimination (FME)
FME can test whether a linear program is feasible.
If the system is feasible, FME can provide a feasible solution by employing back-substitution (in accordance with the lower and upper bounds on the variable that is being eliminated). On the other hand, if the original system is infeasible, the final inequality system will have conflicting lower and upper bounds on the final variable such as and or obvious contradictions like .
FME can optimize linear programs.
To optimize an LP in which we are to maximize , simply add a variable and constraint to our system and make sure to eliminate last. The optimality status (e.g., infeasible, unbounded, an optimal solution) can be obtained from the final inequality system. (How?) Note, however, that Fourier-Motzkin elimination is awfully slow (doubly exponential) and is not a practical means to solve LPs. (But, there is also a singly exponential elimination method.)
Projections of polyhedra are also polyhedra
If we eliminate a variable from a system with inequalities, then we end up with a system of at most inequalities. So, if we start with a finite number of inequalities and variables, then any projection will have finitely many inequalities. (FME may give redundant inequalities, which is okay.)
Projections of rational polyhedra are also rational
If every coefficient and right-hand-side in our original inequality system is rational, then they will remain rational after a variable is eliminated.
More consequences follow by FME, see Kipp Martin’s book. In fact, he develops the basics of LP (e.g., Farkas’ lemma and duality) via projection (FME) and “inverse projection.”