# Parallelizing the dual revised simplex method

arXiv: https://arxiv.org/abs/1503.01889 · HTML: https://mlsanity.com/paper/1503.01889/

## Key facts

- Cited by 89 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Mar 2015.

## Built on by (most cited first, 30 of 89)

- [GOAL: A Generalist Combinatorial Optimization Agent Learner](https://mlsanity.com/paper/2406.15079/) (2024)
- [AlgoTune: Can Language Models Speed Up General-Purpose Numerical Programs?](https://mlsanity.com/paper/2507.15887/) (2025)
- [How to Select Datapoints for Efficient Human Evaluation of NLG Models?](https://mlsanity.com/paper/2501.18251/) (2025)
- [Pushing the limits of fairness impossibility: Who's the fairest of them all?](https://mlsanity.com/paper/2208.12606/) (2022)
- [Toward Sustainable GenAI using Generation Directives for Carbon-Friendly Large Language Model Inference](https://mlsanity.com/paper/2403.12900/) (2024)
- [Efficient Training-Free Online Routing for High-Volume Multi-LLM Serving](https://mlsanity.com/paper/2509.02718/) (2025)
- [A Unified View of Evaluation Metrics for Structured Prediction](https://mlsanity.com/paper/2310.13793/) (2023)
- [PGLearn -- An Open-Source Learning Toolkit for Optimal Power Flow](https://mlsanity.com/paper/2505.22825/) (2025)
- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [Differentiation Through Black-Box Quadratic Programming Solvers](https://mlsanity.com/paper/2410.06324/) (2024)
- [Hierarchical Refinement: Optimal Transport to Infinity and Beyond](https://mlsanity.com/paper/2503.03025/) (2025)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [FastDOG: Fast Discrete Optimization on GPU](https://mlsanity.com/paper/2111.10270/) (2021)
- [Towards Superior Quantization Accuracy: A Layer-sensitive Approach](https://mlsanity.com/paper/2503.06518/) (2025)
- [Provably data-driven projection method for quadratic programming](https://mlsanity.com/paper/2509.04524/) (2025)
- [Automated conjecturing with TxGraffiti](https://mlsanity.com/paper/2409.19379/) (2024)
- [FraPPE: Fast and Efficient Preference-based Pure Exploration](https://mlsanity.com/paper/2508.16487/) (2025)
- [Wasserstein t-SNE](https://mlsanity.com/paper/2205.07531/) (2022)
- [Convex mixed-integer optimization with Frank-Wolfe methods](https://mlsanity.com/paper/2208.11010/) (2022)
- [Differentiable Cutting-plane Layers for Mixed-integer Linear Optimization](https://mlsanity.com/paper/2311.03350/) (2023)
- [OCCAM: Towards Cost-Efficient and Accuracy-Aware Classification Inference](https://mlsanity.com/paper/2406.04508/) (2024)
- [Prima.cpp: Fast 30-70B LLM Inference on Heterogeneous and Low-Resource Home Clusters](https://mlsanity.com/paper/2504.08791/) (2025)
- [Best-of-∞ -- Asymptotic Performance of Test-Time LLM Ensembling](https://mlsanity.com/paper/2509.21091/) (2025)
- [A General and Streamlined Differentiable Optimization Framework](https://mlsanity.com/paper/2510.25986/) (2025)
- [Guided Game Level Repair via Explainable AI](https://mlsanity.com/paper/2410.23101/) (2024)
- [Tightening optimality gap with confidence through conformal prediction](https://mlsanity.com/paper/2503.04071/) (2025)
- [Sobolev Training of End-to-End Optimization Proxies](https://mlsanity.com/paper/2505.11342/) (2025)
- [MathOptAI.jl: Embed trained machine learning predictors into JuMP models](https://mlsanity.com/paper/2507.03159/) (2025)
- [DeepC4: Deep Conditional Census-Constrained Clustering for Large-scale Multitask Spatial Disaggregation of Urban Morphology](https://mlsanity.com/paper/2507.22554/) (2025)
- [Global Resolution: Optimal Multi-Draft Speculative Sampling via Convex Minimization](https://mlsanity.com/paper/2511.15898/) (2025)

## Abstract (arXiv)

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.