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
(50)- On active-set methods for quadratic problems with positive semidefinite matrices
- Progress in mathematical programming solvers from 2001 to 2020
- An equilibrium dynamic traffic assignment model with linear programming formulation
- A parallel primal-dual simplex algorithm
- Advances in the parallelization of the simplex method
- Parallelization of the FICO Xpress-Optimizer
- 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
- Random projections for linear programming: an improved retrieval phase
- GBOML: a structure-exploiting optimization modelling language in Python
- On a Frank-Wolfe approach for abs-smooth functions
- Parallelizing the Dual Simplex Method
- Complexity of chess domination problems
- Generalized measures of population synchrony
- Parallel search paths for the simplex algorithm
- A DRS-based path-following algorithm for linear programming
- Code-verification techniques for the method-of-moments implementation of the magnetic-field integral equation
- Spanning and splitting: integer semidefinite programming for the quadratic minimum spanning tree problem
- An optimization-based algorithm for fair and calibrated synthetic data generation
- A triangulation and fill-reducing initialization procedure for the simplex algorithm
- Convex mixed-integer optimization with Frank-Wolfe methods
- 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
- PACE solver description: UzL exact solver for one-sided crossing minimization
- Portfolio optimization with robust stochastic dominance testing: a genetic algorithm approach
- Absolute value equations with data uncertainty in the l₁ and l_\infty norm balls
- Towards a practical parallelisation of the simplex method
- COAP 2013 Best Paper Prize
- 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
- Meshless moment-free quadrature formulas arising from numerical differentiation
- JuMP 1.0: recent improvements to a modeling language for mathematical optimization
- Decomposition methods for global solution of mixed-integer linear programs
- Distance-restricted firefighting on finite graphs
- Solving multi-stage stochastic facility location problems with modular capacity adjustments
- Exact algorithms for the satellite image selection problem
- Extreme values of the mass distribution associated with d-quasi-copulas via linear programming
- Efficient GPU-based implementations of simplex type algorithms
- A parallel implementation of the revised simplex algorithm using OpenMP: some preliminary results
- Local-MIP: efficient local search for mixed integer programming
- 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
- Randomized quasi-Monte Carlo methods for risk-averse stochastic optimization
- 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)
