Solving Staircase Linear Programs by a Nested Block-Angular Method
Abstract
The objective of the paper is to have a compact inverse representation of the basis of a staircase structure. Every other step in the staircase is assigned to a subsystem partition and the remaining to a master partition. This permits an extension of the generalized upper-bounding technique to be applied. After a column elimination, the resulting working basis associated with the master partition turns out to also have a staircase formate but with half the number of steps. This permits reapplication of the same technique recursively until the number of steps of the pth working basis has only one step. An interesting aspect of the procedure is that a number of operations can be performed in parallel and are not affected by a change in basis.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1973
- Accession Number
- AD0758657
Entities
People
- George Bernard Dantzig
Organizations
- Stanford University