Efficient Coding of the Danzig-Wolfe Decomposition (Linear Programming) Algorithm

Abstract

The Dantzig-Wolfe decomposition (linear programming) principle published in 1960 involves the solving of large-scale mathematical programming problems of particular structure. Large practical problems of this type typically involve many constraints and a large number of variables. For instance, a manufacturer who manufactures various types of household items (thus having many decision variables) may be faced with a multiplant production and distribution problem, needing to maximize profits subject to many constraints such as factory capacities, market potential, raw material availability, budgetary limitations and legal requirements; of which the coupling constraints. (constraints used to link the common resources) may arise from common budgetary limitations on the plants, from common capital used for expansion, or from demands for products whose production involves more than one plant.