PRIMAL PARTITION PROGRAMMING FOR BLOCK DIAGONAL MATRICES,

The complete linear l-block problem in the dual form and the complete primal problem corresponding to it are considered. Since both are dual linear problems, an optimum solution to either one also gives an optimum solution to the other. The method of solution described gives a sequence of feasible solutions to the former which are obtained by solving subproblems of the latter. At each cycle a test is made for a complete problem optimum solution. When this test is satisfied, the optimum solution to both is given. The solution method is summarized and illustrated by means of a two-block example. The solution algorithm is described in detail. The validity of this algorithm is demonstrated by means of the three theorems. Theorem 1 shows that there is an optimum solution to both problems if, and only if, the optimality test is satisfied. The proof that a basis change is made in every nonoptimal block is given in Theorem 2. In Theorem 3 it is shown that the optimum solution is obtained after a finite sequence of nondecreasing function values. The computational results obtained with this method are summarized. Author