Linear Programming with Linked Lists and Automatic Guberization.
Abstract
Linked Lists are used to carry the nonzero elements of the basis inverse in the execution of a linear programming algorithm. The number of nonzero elements needed to execute the algorithm can be reduced by: (1) Using the kernel (a submatrix of the basis inverse); (2) Converting the problem to an equivalent generalized GUB problem; (3) Using a new method to carry range restricted constraints. Computational results indicate that basis inverses are not as dense as commonly assumed; the density is related to the density of the conflict matrix corresponding to the coefficient matrix; the nonzero buildup can be significantly reducing using the method noted above. A comparison of algorithms used to locate disjoint subsets of constraints is made.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1975
- Accession Number
- ADA015918
Entities
People
- Richard D. Mcbride
Organizations
- University of Southern California