Basis Factorization for Block-Angular Linear Programs: Unified Theory of Partitioning and Decomposition Using the Simplex Method.

摘要

A general block-angular basis factorization is developed to represent the inverse of the basis of block-angular linear problems in factorized form. This factorization takes advantage of the structure of the matrix and can be efficiently updated when one column is replaced by another. Partitioning and decomposition methods (excluding Dantzig-Wolfe decomposition) for block-angular linear problems with coupling constraints, or coupling variables, or both, are shown to be variants of a Simplex Method using this general block-angular basis factorization form of the inverse, with various criteria as to the vector pair selected to enter and to leave the basis. By considering other criteria new algorithms are obtained. In particular, algorithms are presented for which at each iteration only a subset of the terms in the factorization needs to be used or to be updated. Preliminary experimental results with such an algorithm for block-angular linear problems with coupling constraints are included. Results are extended to the case when imbedded in the block-angular structures there are blocks which themselves are of block-angular form. Applications to the solution of dynamic linear programs (staircase structure) are developed.