A Basis Factorization Method for Block Triangular Linear Programs.
André F. Perold, George B. Dantzig · Defense Technical Information Center (DTIC) · 1978
Time-staged and multi-staged linear programs usually have a structure that is block triangular. Basic solutions to such problems typically have the property that similar type activities persist in the basis over several consecutive time-periods. When this occurs the basis is close to being square block triangular. In 1955 Dantzig suggested a way of factorizing the basis to take advantage of this property. This paper discusses persistance in staircase models and then presents a considerable refinement of the above factorization algorithm. The method has been implemented in an experimental code, with use being made of LU and QR factorization and updating techniques for the solution of small sub-systems of equations. An in-depth analysis is made of the work involved, and computational experience on several dynamic models is reported. (Author)