PRIMAL-DUAL DECOMPOSITION PROGRAMMING.

A primal-dual method for solving linear programs with a block-angular matrix structure is presented which employs the Decomposition Principle of Dantzig and Wolfe, who first studied this structure. Preliminary results indicate that the proposed method is more efficient than the standard decomposition method which uses the twophase simplex method to solve an equivalent extremal program with a reduced basis size whose coefficients are generated through the solution of linear subprograms. By contrast, the proposed method employs a primal-dual method and the coefficients are generated through subprograms with nonlinear objectives. These subprograms involve the maximization of a quotient of two linear functions subject to linear constraints in nonegative variables. Such problems are known as linear-fractional, rational objective, or hyperbolic programs and can be solved as a variant of standard linear programming. Under the conditions imposed by the primal-dual method, special parametric techniques can be employed to take advantage of particular matrix structures, such as the transportation structure, exhibited by the subprograms. Author