Accession Number:

AD0269699

Title:

A DUAL DECOMPOSITION PRINCIPLE

Descriptive Note:

Corporate Author:

RENSSELAER POLYTECHNIC INST TROY NY

Personal Author(s):

Report Date:

1961-12-04

Pagination or Media Count:

20.0

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE