A DUAL DECOMPOSITION PRINCIPLE
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 04, 1961
- Accession Number
- AD0269699
Entities
People
- C. E. Lemke
- T. J. Powers
Organizations
- Rensselaer Polytechnic Institute