Hyper-sparsity in the revised simplex method and how to exploit it

DOI10.1007/s10589-005-4802-0zbMath1125.90033MaRDI QIDQ2490370

K. I. M. McKinnon, J. A. J. Hall

Publication date: 2 May 2006

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-005-4802-0

zbMATH Keywords

linear programming; sparsity; revised simplex method

Mathematics Subject Classification ID

65F50: Computational methods for sparse matrices

90C06: Large-scale problems in mathematical programming

90C05: Linear programming

Related Items

Interior point methods 25 years later, Mixed integer programming: A historical perspective with Xpress-MP, Towards a practical parallelisation of the simplex method, Progress in the dual simplex algorithm for solving large scale LP problems: Techniques for a fast and stable implementation, Dual multilevel optimization, Preconditioning indefinite systems in interior point methods for large scale linear optimisation

Uses Software

• SoPlex
• CPLEX
• KORBX
• Benchmarks for Optimization Software
• DEVEX
• NETGEN

Cites Work

• Unnamed Item
• Unnamed Item
• Steepest-edge simplex algorithms for linear programming
• A stabilization of the simplex method
• A Decomposition-Based Pricing Procedure for Large-Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem
• Solving Real-World Linear Programs: A Decade and More of Progress
• Sparse Partial Pivoting in Time Proportional to Arithmetic Operations
• Matrix augmentation and partitioning in the updating of the basis inverse
• Solving Multicommodity Flow Problems with a Primal Embedded Network Simplex Algorithm
• Updated triangular factors of the basis to maintain sparsity in the product form simplex method
• Pivoting for Size and Sparsity in Linear Programming Inversion Routes
• Pivot selection methods of the Devex LP code
• The Product Form for the Inverse in the Simplex Method