de
en
Schliessen
Detailsuche
Bibliotheken
Projekt
Impressum
Datenschutz
Schliessen
Publizieren
Besondere Sammlungen
Digitalisierungsservice
Hilfe
Impressum
Datenschutz
zum Inhalt
Detailsuche
Schnellsuche:
OK
Ergebnisliste
Titel
Titel
Inhalt
Inhalt
Seite
Seite
Im Werk suchen
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
Basic idea
Neighboring solutions
Pricing
Ratio test
Basis change
Algorithmic descriptions
The Bound Flipping Ratio Test
Dual steepest edge pricing
Elaborated version of the Dual Simplex Algorithm
Dual Phase I Methods
Introduction
Big-M method
Dual feasibility correction
Minimizing the sum of dual infeasibilities
Subproblem approach
Algorithmic approach
Artificial bounds
Cost modification
Pan's method
Computational techniques
Solving Systems of Linear Equations
Introduction
Product form of the inverse
LU decomposition
LU factorization
LU update
Forrest/Tomlin update
Suhl/Suhl update
Exploiting (hyper-)sparsity in FTran, BTran and LU-update
Algorithms for sparse and hypersparse triangular systems
FTran and BTran with Suhl/Suhl update
Numerical Stability and Degeneracy
Introduction
Numerical stability
Degeneracy and cycling
Techniques to ensure numerical stability
Numerical tolerances
Stabilizing ratio tests
Modified standard ratio test
Harris' ratio test
Shifting
Stabilizing bound flipping ratio test
Refactorization, accuracy checks and stability control
Refactorization for speed
Refactorization for stability
Techniques to reduce degeneracy and prevent cycling
Perturbation
Randomized pricing
Further computational aspects
LP preprocessing, scaling and crash procedures
Computation of the pivot row
Implementation and results
Implementation
The Mathematical OPtimization System MOPS
MOPS and its history
External system architecture
LP / MIP solution framework
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
Die detaillierte Suchanfrage erfordert aktiviertes Javascript.