Triangular Factorization and Generalized Upper Bounding Techniques

We develop a compact inverse method for linear programming problems having block triangular or sparse constraint matrices. Special cases of the method are, for example, the generalized upper bounding technique and its extensions. For these methods we show how a triangular factorization can be used f...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1977-01, Vol.25 (1), p.89-99
Main Authors: Kallio, Markku, Porteus, Evan L
Format: Article
Language:English
Subjects:
Factorization
Linear programming
Mathematical procedures
Research universities
Simplex method
Staircases
Studies
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We develop a compact inverse method for linear programming problems having block triangular or sparse constraint matrices. Special cases of the method are, for example, the generalized upper bounding technique and its extensions. For these methods we show how a triangular factorization can be used for the working basis and block bases. In this case (and even if the constraint matrix has no special structure) our method becomes a variation of the revised simplex method using a single triangular factorization of the basis. However, the updating procedure of the triangular factors differs from existing ones in a way that implies that certain structures are exploited naturally.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.25.1.89