Decomposition Principle for Linear Programs

George B. Dantzig and Philip Wolfe
Additional contact information
George B. Dantzig: The Band Corporation, Santa Monica, California
Philip Wolfe: The Band Corporation, Santa Monica, California

Operations Research, 1960, vol. 8, issue 1, 101-111

Abstract: A technique is presented for the decomposition of a linear program that permits the problem to be solved by alternate solutions of linear sub-programs representing its several parts and a coordinating program that is obtained from the parts by linear transformations. The coordinating program generates at each cycle new objective forms for each part, and each part generates in turn (from its optimal basic feasible solutions) new activities (columns) for the interconnecting program. Viewed as an instance of a “generalized programming problem” whose columns are drawn freely from given convex sets, such a problem can be studied by an appropriate generalization of the duality theorem for linear programming, which permits a sharp distinction to be made between those constraints that pertain only to a part of the problem and those that connect its parts. This leads to a generalization of the Simplex Algorithm, for which the decomposition procedure becomes a special case. Besides holding promise for the efficient computation of large-scale systems, the principle yields a certain rationale for the “decentralized decision process” in the theory of the firm. Formally the prices generated by the coordinating program cause the manager of each part to look for a “pure” sub-program analogue of pure strategy in game theory, which he proposes to the coordinator as best he can do. The coordinator finds the optimum “mix” of pure sub-programs (using new proposals and earlier ones) consistent with over-all demands and supply, and thereby generates new prices that again generates new proposals by each of the parts, etc. The iterative process is finite.

Date: 1960
References: Add references at CitEc
Citations: View citations in EconPapers (298)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.8.1.101 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:8:y:1960:i:1:p:101-111

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().