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

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

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

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 programmingsparsityrevised simplex method

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Large-scale problems in mathematical programming (90C06) Linear programming (90C05)

Related Items (14)

Parallel search paths for the simplex algorithm ⋮ Parallelizing the dual revised simplex method ⋮ Computing in Operations Research Using Julia ⋮ Parallel distributed-memory simplex for large-scale stochastic LP problems ⋮ Preconditioning indefinite systems in interior point methods for large scale linear optimisation ⋮ Interior point methods 25 years later ⋮ Implementation of an interior point method with basis preconditioning ⋮ COAP 2013 Best Paper Prize ⋮ Dual multilevel optimization ⋮ 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 ⋮ A decomposition-based approach for the multiperiod multiproduct distribution planning problem ⋮ Novel update techniques for the revised simplex method

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

This page was built for publication: Hyper-sparsity in the revised simplex method and how to exploit it