On the Significance of Solving Linear Programming Problems with Some Integer Variables

Abstract

Abstract : Recent proposals by Gomory and others for solving linear programs involving integer-valued variables appear sufficiently promising that it is worthwhile to systematically review and classify problems that can be reduced to this class and thereby solved. Historically, non-linear, nonconvex and combinatorial problems are areas where classical mathematics almost always fails. It is therefore significant that the reduction can be made for problems involving multiple dichotomies and k-fold alternatives which include problems with discrete variables, non-linear separable minimizing functions, conditional constraints, global minimum of general concave functions and combinatorial problems such as the fixed charge problem, traveling salesman problem, orthogonal latin square problems, and map coloring problems.