Fourier-Motzkin Elimination and Its Dual
STANFORD UNIV CA DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
Research on linear inequalities systems prior to 1947 consisted of isolated efforts by a few investigators. A case in point is the elimination technique for reducing the number of variables in the system. A description of the method can be found in Motzkins 1936 Ph.D. thesis. It differs from its analog for systems of equations in that unfortunately each step in the elimination can greatly increase the number of inequalities in the remaining variables. For years the method was referred to as the Motzkin Elimination Method. However, because of the odd grave-digging custom of looking for artifacts in long forgotten papers, it is now known as the Fourier-Motzkin Elimination Method. In the paper the author reviews the elimination scheme and shows that a dual form of the method is a technique for reducing the number of equations in a system of equations in non-negative variables. Some comments regarding its applicability to integer programs also made.
- Operations Research