A DUAL DECOMPOSITION PRINCIPLE
RENSSELAER POLYTECHNIC INST TROY NY
Pagination or Media Count:
A decomposition principle for linear programming is presented. The technique may be viewed as a dual of the Dantzig - Wolfe decomposition principle for linear programs. The program matrix in what we may call the basic problem is considered as having many an infinite number of columns. One visualizes a basic problem, in primal form, where, the set of permissible columns is not finite, as in the usual primal form, but is a given convex polyhedron. The basic problem is solved by the modified simplex method, but at each iteration the column to enter the current basis emerges as the solution to an auxiliary linear program and is, in fact, an extreme point of the given convex polyhedron.
- Operations Research