Dynamic Factorization in Large-Scale Optimization
Michael P. Olson · 1989
Factorization of linear programming (LP) models enables a large portion of the LP tableau to be represented implicitly and generated from the remainingexplicit part.Dynamic factorization admits algebraicelementswhichchangein dimensionduring the courseof solution.A unifyingmathematical framework for dynamic row factorization is presented with three algorithms which derive from differentLP modelrowstructures: generalizedupper boundrows, pure networkrows, and generalized networkTOWS.Eachof these structuresis a generalization of its predecessors, and each corresponding algorithm exhibitsjust enough additional richness to accommodate the structure at hand within the unifledframework.Implementation and computational results arepresentedfor a varietyof real-world models.Theseresultssuggestthateach of these algorithmsis superiorto the traditional, non-factorized approach, with the degreeof improvement dependingupon thesize and qualityof the row factorization identified.