Solving Staircase Linear Programs by a Nested Block-Angular Method
STANFORD UNIV CA DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
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.
- Operations Research