Fourier-Motzkin elimination

From Glossary

Jump to: navigation, search

A procedure by which a variable is eliminated in a system of linear inequalities. The remaining inequalities, which include some new ones, has a solution if and only if the original system has a solution. Eventually, this reduces to one variable or an inconsistency is determined during the elimination. The one variable can be assigned any value in its range, then a backtracking procedure can be executed to obtain values of the other variables, which were eliminated. Originally presented by Fourier in 1826, Motzkin analyzed it in 1933 in light of new developments of the theory of linear inequalities to solve linear programs. Its computational complexity is exponential, and it gave way to the simplex method.

Personal tools