Dynamic Factorization in Large-Scale Optimization
Loading...
Authors
Brown, Gerald G.
Olson, Michael P.
Subjects
Advisors
Date of Issue
1993-03-12
Date
March 15, 1990 (Revised March 12, 1993)
Publisher
Naval Postgraduate School, Monterey, CA
Language
Abstract
Factorization of linear programming (LP) models enables a large portion of the LP tableau to be represented implicitly and generated from the remaining explicit part. Dynamic factorization admits algebraic elements which change in dimension during the course of solution. A unifying mathematical framework for dynamic row factorization is presented with three algorithms which derive from different LP model row structures: generalized upper bound rows, pure network rows, and generalized network rows. Each of these structures is a generalization of its predecessors, and each corresponding algorithm exhibits just enough additional richness to accommodate the structure at hand within the unified framework. Implementation and computational results are presented for a variety of real-world models. These results suggest that each of these algorithms is superior to the traditional, non-factorized approach, with the degree of improvement depending upon the size and quality of the row factorization identified.
Type
Report
Description
Missing page 32.
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
NPS OR-93-008
Sponsors
Air Force Office of Scientific Research
Chief of Naval Research
Chief of Naval Research
Funder
AFOSR - MIPR-92-0007
CNR - N0007493WR24006
CNR - N0007493WR24006
Format
42 p.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.