返回Google圖書搜尋

Basis Factorization for Block-angular Linear Programs

其他書名	Unified Theory of Partitioning and Decomposition Using the Simplex Method
出版	IIASA, 1974
URL	http://books.google.com.hk/books?id=atEEAAAAIAAJ&hl=&source=gbs_api

註釋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.