Dynamic Factorization in Large-Scale Optimization

Abstract

Factorization is an approach to linear programming (LP) in which the algebraic elements of the LP tableau are organized in such a way that a large portion of the tableau may be represented implicitly and generated from the remaining explicit part. In dynamic row factorization, the row structure of the LP model instance influences the algebraic structure of the tableau, and the dimension of the algebraic elements may change as the solution progresses. We present three algorithms motivated by this approach, each resulting from a different LPL model row structure: generalized upper bound (GUB) rows, pure network rows and generalized network rows. We describe implementations of all three algorithms, specifying data structures for tableau and basis inverse representations and detailing procedures for manipulation and update of these representations.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1989
Accession Number
ADA214568

Entities

People

  • Michael P. Olson

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Classification
  • Computations
  • Computer Programming
  • Efficiency
  • Evolutionary Algorithms
  • Identification
  • Integer Programming
  • Linear Programming
  • Linear Systems
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Optimization
  • Simplex Method
  • United States

Readers

  • Linear Algebra
  • Operations Research