Persistent Link:
http://hdl.handle.net/10150/187870
Title:
DOUBLE-BASIS SIMPLEX METHOD FOR LARGE SCALE LINEAR PROGRAMMING.
Author:
PROCTOR, PAUL EDWARD.
Issue Date:
1982
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
The basis handling procedures of the simplex method are formulated in terms of a "double basis". That is, the basis is factored as (DIAGRAM OMITTED...PLEASE SEE DAI) where ‘B, the pseudobasis matrix, is the basis matrix at the last refactorization. P and Q are permutation matrices. Forward and backward transformations and update are presented for each of two implementations of the double-basis method. The first implementation utilizes an explicit G⁻¹ matrix. The second uses a sparse LU factorization of G. Both are based on Marsten's modularized XMP package, in which standard simplex method routines are replaced by corresponding double-basis method routines. XMP and the LU double-basis method implementation employ Reid's LA05 routines for handling sparse linear programming bases. All calculations are done without reference to the H matrix. Therefore, the update is restricted to G, which has dimension limited by the refactorization frequency, and P and Q, which are held as lists. This can lead to a saving in storage space and updating time. The cost is that time for transformations will be about double. Computational comparisons of storage and speed performance are made with the standard simplex method on problems of up to 1480 constraints. It is found that, generally, the double-basis method performs best on larger, denser problems. Density seems to be the more important factor, and the problems with large nonzero growth between refactorizations are the better ones for the double-basis method. Storage saving in the basis inverse representation versus the standard method is as high as 36%, whereas the double-basis run times are 1.2 or more times as great.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Linear programming.; Matrices -- Mathematical models.; Programming (Mathematics)
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Applied Mathematics; Graduate College
Degree Grantor:
University of Arizona

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleDOUBLE-BASIS SIMPLEX METHOD FOR LARGE SCALE LINEAR PROGRAMMING.en_US
dc.creatorPROCTOR, PAUL EDWARD.en_US
dc.contributor.authorPROCTOR, PAUL EDWARD.en_US
dc.date.issued1982en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractThe basis handling procedures of the simplex method are formulated in terms of a "double basis". That is, the basis is factored as (DIAGRAM OMITTED...PLEASE SEE DAI) where ‘B, the pseudobasis matrix, is the basis matrix at the last refactorization. P and Q are permutation matrices. Forward and backward transformations and update are presented for each of two implementations of the double-basis method. The first implementation utilizes an explicit G⁻¹ matrix. The second uses a sparse LU factorization of G. Both are based on Marsten's modularized XMP package, in which standard simplex method routines are replaced by corresponding double-basis method routines. XMP and the LU double-basis method implementation employ Reid's LA05 routines for handling sparse linear programming bases. All calculations are done without reference to the H matrix. Therefore, the update is restricted to G, which has dimension limited by the refactorization frequency, and P and Q, which are held as lists. This can lead to a saving in storage space and updating time. The cost is that time for transformations will be about double. Computational comparisons of storage and speed performance are made with the standard simplex method on problems of up to 1480 constraints. It is found that, generally, the double-basis method performs best on larger, denser problems. Density seems to be the more important factor, and the problems with large nonzero growth between refactorizations are the better ones for the double-basis method. Storage saving in the basis inverse representation versus the standard method is as high as 36%, whereas the double-basis run times are 1.2 or more times as great.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectLinear programming.en_US
dc.subjectMatrices -- Mathematical models.en_US
dc.subjectProgramming (Mathematics)en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineApplied Mathematicsen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.identifier.proquest8217460en_US
dc.identifier.oclc681967100en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.