DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
AD0269699
Title:
A DUAL DECOMPOSITION PRINCIPLE
Corporate Author:
RENSSELAER POLYTECHNIC INST TROY NY
Report Date:
1961-12-04
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.
Pages:
0020
Distribution Statement:
Approved for public release; distribution is unlimited.
Contract Number:
NONR-591(13)
File Size:
0.77MB
