Fourier-Motzkin Elimination and Its Dual
Abstract
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 Motzkin's 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1972
- Accession Number
- AD0750674
Entities
People
- George Bernard Dantzig
Organizations
- Stanford University