Accession Number : AD0625365

Title :   PRIMAL-DUAL DECOMPOSITION PROGRAMMING.

Descriptive Note : Research rept.,

Corporate Author : OPERATIONS RESEARCH CENTER UNIV OF CALIF BERKELEY

Personal Author(s) : Bell,Earl J.

Report Date : AUG 1965

Pagination or Media Count : 42

Abstract : 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)

Descriptors :   (*LINEAR PROGRAMMING, OPTIMIZATION), MATRICES(MATHEMATICS), SCHEDULING, CALCULUS OF VARIATIONS, TRANSPORTATION, ALGORITHMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE