Parallelizing the dual revised simplex method
From MaRDI portal
Abstract: This paper introduces the design and implementation of two parallel dual simplex solvers for general large scale sparse linear programming problems. One approach, called PAMI, extends a relatively unknown pivoting strategy called suboptimization and exploits parallelism across multiple iterations. The other, called SIP, exploits purely single iteration parallelism by overlapping computational components when possible. Computational results show that the performance of PAMI is superior to that of the leading open-source simplex solver, and that SIP complements PAMI in achieving speedup when PAMI results in slowdown. One of the authors has implemented the techniques underlying PAMI within the FICO Xpress simplex solver and this paper presents computational results demonstrating their value. This performance increase is sufficiently valuable for the achievement to be used as the basis of promotional material by FICO. In developing the first parallel revised simplex solver of general utility and commercial importance, this work represents a significant achievement in computational optimization.
Recommendations
Cites work
- scientific article; zbMATH DE number 3554052 (Why is no real title available?)
- scientific article; zbMATH DE number 1041084 (Why is no real title available?)
- ASYNPLEX, an asynchronous parallel revised simplex algorithm
- COIN-OR
- Evolution of linear programming computing techniques
- Hyper-sparsity in the revised simplex method and how to exploit it
- Novel update techniques for the revised simplex method
- Parallelizing the Dual Simplex Method
- Pivot selection methods of the Devex LP code
- Progress in the dual simplex algorithm for solving large scale LP problems: Techniques for a fast and stable implementation
- Steepest-edge simplex algorithms for linear programming
- Towards a practical parallelisation of the simplex method
- Updated triangular factors of the basis to maintain sparsity in the product form simplex method
Cited in
(26)- Progress in mathematical programming solvers from 2001 to 2020
- A parallel primal-dual simplex algorithm
- Advances in the parallelization of the simplex method
- Parallelization of the FICO Xpress-Optimizer
- Random projections for linear programming: an improved retrieval phase
- GBOML: a structure-exploiting optimization modelling language in Python
- Parallelizing the Dual Simplex Method
- Parallel search paths for the simplex algorithm
- Code-verification techniques for the method-of-moments implementation of the magnetic-field integral equation
- A triangulation and fill-reducing initialization procedure for the simplex algorithm
- HiGHS
- Parallelization of the FICO Xpress-Optimizer
- The `Idiot' crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems
- High-dimensional composite quantile regression: optimal statistical guarantees and fast algorithms
- Absolute value equations with data uncertainty in the $l_1$ and $l_\infty$ norm balls
- Towards a practical parallelisation of the simplex method
- COAP 2013 Best Paper Prize
- JuMP 1.0: recent improvements to a modeling language for mathematical optimization
- Decomposition methods for global solution of mixed-integer linear programs
- Efficient GPU-based implementations of simplex type algorithms
- A parallel implementation of the revised simplex algorithm using OpenMP: some preliminary results
- A practitioner's guide to MDP model checking algorithms
- On the essence of parallel independence for the double-pushout and sesqui-pushout approaches
- P<scp>a</scp>PILO: A Parallel Presolving Library for Integer and Linear Optimization with Multiprecision Support
- Predicer: abstract stochastic optimisation model framework for multi-market operation
- KidneyExchange.jl: a Julia package for solving the kidney exchange problem with branch-and-price
Describes a project that uses
Uses Software
This page was built for publication: Parallelizing the dual revised simplex method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1646685)
