A Basis Factorization Method for Block Triangular Linear Programs.

Abstract

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1978
Accession Number
ADA060976

Entities

People

  • Andre F. Perold
  • George Bernard Dantzig

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms
  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Computations
  • Computer Programming
  • Differential Equations
  • Equations
  • Linear Accelerators
  • Linear Algebra
  • Linear Programming
  • Mathematical Programming
  • New York
  • Operations Research
  • Plastic Explosives
  • Probability
  • Probability Distributions
  • Simplex Method
  • United States

Fields of Study

  • Computer science

Readers

  • Linear Algebra
  • Operations Research
  • Theoretical Analysis.