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
- ASYNPLEX, an asynchronous parallel revised simplex algorithm
- COIN-OR
- Evolution of linear programming computing techniques
- scientific article; zbMATH DE number 3554052 (Why is no real title available?)
- scientific article; zbMATH DE number 1041084 (Why is no real title available?)
- 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
(59)- HiGHS
- A parallel primal-dual simplex algorithm
- Parallel search paths for the simplex algorithm
- On the essence of parallel independence for the double-pushout and sesqui-pushout approaches
- A triangulation and fill-reducing initialization procedure for the simplex algorithm
- Code-verification techniques for the method-of-moments implementation of the magnetic-field integral equation
- Parallelization of the FICO Xpress-Optimizer
- Advances in the parallelization of the simplex method
- scientific article; zbMATH DE number 1041084 (Why is no real title available?)
- Parallelizing the Dual Simplex Method
- A parallel implementation of the revised simplex algorithm using OpenMP: some preliminary results
- Parallelization of the FICO Xpress-Optimizer
- COAP 2013 Best Paper Prize
- The `Idiot' crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems
- Absolute value equations with data uncertainty in the l₁ and l_\infty norm balls
- JuMP 1.0: recent improvements to a modeling language for mathematical optimization
- Progress in mathematical programming solvers from 2001 to 2020
- P<scp>a</scp>PILO: A Parallel Presolving Library for Integer and Linear Optimization with Multiprecision Support
- High-dimensional composite quantile regression: optimal statistical guarantees and fast algorithms
- Decomposition methods for global solution of mixed-integer linear programs
- A practitioner's guide to MDP model checking algorithms
- 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
- Random projections for linear programming: an improved retrieval phase
- GBOML: a structure-exploiting optimization modelling language in Python
- Homotopy.io: a proof assistant for finitely-presented globular n-categories
- Constructing tight quadratic relaxations for global optimization. II: underestimating difference-of-convex (D.C.) functions
- Implied integrality in mixed-integer optimization
- Distance-restricted firefighting on finite graphs
- Solving multi-stage stochastic facility location problems with modular capacity adjustments
- Convex mixed-integer optimization with Frank-Wolfe methods
- Exact algorithms for the satellite image selection problem
- Extreme values of the mass distribution associated with d-quasi-copulas via linear programming
- Meshless moment-free quadrature formulas arising from numerical differentiation
- Local-MIP: efficient local search for mixed integer programming
- On active-set methods for quadratic problems with positive semidefinite matrices
- An equilibrium dynamic traffic assignment model with linear programming formulation
- Randomized quasi-Monte Carlo methods for risk-averse stochastic optimization
- Minimax estimation of partially-observed vector autoregressions
- Last fifty years of integer linear programming: a focus on recent practical advances
- Uncertainty reduction in robust optimization
- Complexity of chess domination problems
- Generalized measures of population synchrony
- A DRS-based path-following algorithm for linear programming
- Spanning and splitting: integer semidefinite programming for the quadratic minimum spanning tree problem
- An optimization-based algorithm for fair and calibrated synthetic data generation
- On a Frank-Wolfe approach for abs-smooth functions
- PACE solver description: UzL exact solver for one-sided crossing minimization
- Portfolio optimization with robust stochastic dominance testing: a genetic algorithm approach
- Extreme strong branching for QCQPs
- NashOpt: a Python library for computing generalized Nash equilibria
- On the nonconvexity issue in the radial Calderón problem
- Row-Polar LP-Newton for Linear Programming with Corral Repair
- Verified Linear Programming through Tolerance-Aware Precision Boosting
- A convex numerical scheme for the Evans-Gangbo transport-density system, in one, two, and three dimensions
- Automated conjecturing with TxGraffiti
- PACE solver description: HitS\&DoSeS -- exact and heuristic solvers for the dominating set and hitting set problems
- Efficient GPU-based implementations of simplex type algorithms
- Towards a practical parallelisation of the simplex method
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)
