The decomposition principle for linear programs

Abstract

Abstract The decomposition algorithm of Dantzig and Wolfe is a procedure for the solution of linear programs using a generalized extension of the simplex method. In this paper the algorithm is described and a worked numerical example given. No new results are presented. The paper is intended to further publicise the method. The terminology used is that agreed upon by the participants at a workshop on the decomposition algorithm held by Mathematica in February, 1962 under the sponsorship of the Special Interest Group of Mathematical Programming of the Association of Computing Machinery.