Parallelizing the dual revised simplex method

Q. Huangfu and J. A. J. Hall, Mathematical Programming Computation 10(1):119–142, 2018 (DOI 10.1007/s12532-017-0130-5; preprint arXiv:1503.01889). The peer-reviewed engine paper behind highs — read from the preprint PDF.

This closes the half of coverage edge 4 that was still open. The edge wanted "a T1 chapter on simplex/branch-and-bound" because linear-programming and integer-programming rest on Wikipedia. It also wanted a solver page, and that half had already been closed on 2026-08-10 by highs — the edge text was three weeks stale when this hunt started, which is the fourth instance this week of a growth edge outliving the source that answered it.

Why parallelising this was thought impossible

The revised simplex method is preferred over the tableau form on sparse problems because it exploits hyper-sparsity, and that is exactly what resists parallelism: the standard simplex method has been parallelised repeatedly with speedups "ranging from tens to up to a thousand", while the revised method has seen "less success". The paper states the prior consensus flatly — "since scalable speedup for general large sparse LP problems appears unachievable, the revised simplex method has been considered unsuitable for parallelisation." Its answer is not to chase scalability but to take what a desktop already has: "when every desktop computer is a multi-core machine, any speedup is desirable."

Two schemes. PAMI revives suboptimization, a pivoting strategy the paper calls "relatively unknown", to get parallelism across iterations. SIP overlaps components within a single iteration. They are complements, not alternatives.

The numbers, on 30 problems

The reference set is 30 LP problems, most from Mittelmann's representative list — the same Mittelmann this spoke already holds as mittelmann-benchmarks, eight years earlier. Mean relative solution times:

PAMI is "twice as fast in parallel" on more than 65% of the set. The result the paper flags itself is the one to keep: PAMI in serial is worse than hsol (mean 0.64 in its favour), and still wins on 8 cores. The suboptimization strategy wastes computation per iteration and buys back more than it wastes by running iterations concurrently. A cutoff factor of 0.95 on candidate quality is what keeps the wasted work bounded; the paper found it by experiment, and reports that lowering it degrades the mean speedup while the large-speedup counts stay stable until 0.9.

The disclosure, which the corpus should keep

Huangfu's affiliation on the paper is FICO, not a university. The abstract says so outright: the techniques "underlying PAMI" were implemented in the FICO Xpress simplex solver, and "this performance increase is sufficiently valuable for the achievement to be used as the basis of promotional material by FICO."

That is a peer-reviewed paper stating its own commercial stake in the result, in the abstract, in a journal that publishes the software alongside the article. Set it beside the hub's standing "nobody re-runs anybody's numbers" item: this is neither the vendor benchmark that item complains about nor the independent re-run it looks for. It is a third arrangement — a conflicted author, declared, in a venue that requires reproducible artifacts — and the declaration is what makes it usable. Compare DOAm, where the author's own modification tops the author's own suite with no such statement anywhere.

What it gives the spoke

highs carries the ranking; this carries the mechanism. The page could previously say HiGHS is 12.8× off COPT on LP and 5.44× on MILP without saying what HiGHS does, and the project site "claims high performance and publishes no numbers of its own." Now the corpus holds the design, the strategy, the tuning constant, and the honest negative result inside it.

It also gives the exact-methods tradition a T1 primary of the kind the metaheuristics half has had since nfl-original-paper and nsga-ii. Read against no-free-lunch-theorem: this is what progress looks like inside a fixed problem class where structure is known. Thirty problems, one strategy, a mean of 1.51× — and it was publishable, commercially valuable, and considered impossible beforehand.

Not read: the full computational tables (Tables 4–6 give per-model iteration times and solution times for hsol, PAMI, SIP, Clp and CPLEX), and the LU-update and pricing sections underneath.

Related

highs · linear-programming · integer-programming · mittelmann-benchmarks · miplib · no-free-lunch-theorem · convex-optimization · synthesis