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.

Short cut computational methods are developed for solving systems whose matrices may be generally described as block triangular.

A procedure is presented for the efficient computational solution of linear programs having a certain structural property characteristic of a large class of problems of practical interest. The property makes possible the decomposition of the problem into a sequence of small linear programs whose iterated solutions solve the given problem through a generalization of the simplex method for linear programming. 1. THE DECOMPOSED LINEAR PROGRAM MANY LINEAR programming problems of practical interest have the property that they may be described, in part, as composed of separate linear programming problems tied together by a number of constraints considerably smaller than the total number imposed on the problem. When the matrix of coefficients of such a problem, suitably ordered, is displayed in the usual way, a pattern emerges like that shown in Figure 1. In this figure the constraint matrix has been partitioned into nonzero blocks A1 and By, the right-hand side column of constants correspondingly into b, bl,..., bn; and the costs,