Basis Factorization for Block-Angular Linear Problems: Unified Theory of Partitioning and Decomposition using the Simplex Method

Winkler, C. (1974). Basis Factorization for Block-Angular Linear Problems: Unified Theory of Partitioning and Decomposition using the Simplex Method. IIASA Research Report. IIASA, Laxenburg, Austria: RR-74-022

[thumbnail of RR-74-022.pdf]
Preview
Text
RR-74-022.pdf

Download (2MB) | Preview

Abstract

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 embedded 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.

Item Type: Monograph (IIASA Research Report)
Research Programs: System and Decision Sciences - Core (SDS)
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 01:40
Last Modified: 27 Aug 2021 17:07
URI: https://pure.iiasa.ac.at/72

Actions (login required)

View Item View Item