Dynamic Pricing Criteria in Linear Programming
Abstract
In recent years the interest in linear programming algorithms has increased greatly due to the discovery of new interior-point methods. New results have also prompted researchers to reconsider some previously discarded ideas in light of their additional knowledge. This report begins with a study of some variants of the reduced-gradient method applied to linear programs. Preliminary computational tests revealed how sparsity and degeneracy, two characteristics present in most practical problems, can severely inhibit such variants. The development of dynamic pricing criteria to exclude certain columns from the search direction provides a computationally efficient way to alleviate these difficulties. Application to the simplex method yields a pivot rule designed to avoid degenerate pivots. Generalization of the rule yields a cheap method to estimate the step lengths associated with potential incoming nonbasic variables. The result is a set of pivot rules that appear particularly useful on highly degenerate and poorly scaled linear programs. Extensive computational tests are presented. Keywords: Simplex method.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1988
- Accession Number
- ADA198945
Entities
People
- Edward S. Klotz
Organizations
- Stanford University