The dual simplex method, techniques for a fast and stable implementation / Achim Koberstein. 2005
Inhalt
- Introduction
- Fundamental algorithms
- Foundations
- The linear programming problem and its computational forms
- Geometry
- LP Duality
- Basic solutions, feasibility, degeneracy and optimality
- The Dual Simplex Method
- The Revised Dual Simplex Algorithm
- The Bound Flipping Ratio Test
- Dual steepest edge pricing
- Elaborated version of the Dual Simplex Algorithm
- Dual Phase I Methods
- Computational techniques
- Solving Systems of Linear Equations
- Numerical Stability and Degeneracy
- Introduction
- Techniques to ensure numerical stability
- Techniques to reduce degeneracy and prevent cycling
- Further computational aspects
- Implementation and results
- Implementation
- The Mathematical OPtimization System MOPS
- The dual simplex code
- Basic data structures
- Pricing
- Initialization and update of DSE weights
- Vector of primal infeasibilities
- Partial randomized pricing
- Ratio test
- FTran, BTran, LU-Update and factorization
- Data structures for the LU-factors
- Exploiting hypersparsity
- Forward Transformation (FTran)
- LU-update and factorization
- Overview
- Numerical results
- Test problems
- Performance measures
- Study on dual phase 1
- Chronological progress study
- Overall benchmarks
- Summary and Conclusion
- Bibliography
- Tables