The Decomposition Algorithm for Linear Programs

TLDR

Many linear programming problems can be decomposed into smaller LPs linked by few constraints, with the coefficient matrix exhibiting a block structure. The paper presents a procedure for efficiently solving linear programs that possess this decomposable structure, applicable to a large class of practical problems. The method decomposes the problem into a sequence of small linear programs by partitioning the constraint matrix into blocks, iteratively solving them in a generalized simplex framework. 1.

Abstract

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,