The Decomposition Algorithm for Linear Programs
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,
- DOI
- 10.2307/1911818
- Volume
- 29 (4)
- Pages
- 767
- Export
- BibTeX
- Sources
- openalex crossref