HiGHS solver improvements speed up finding good mixed-integer solutions
Presolve heuristics in HiGHS: implementation and computational study
Mathematical Software
Summary
Mixed-integer programming problems are a type of math puzzle used to make decisions, like scheduling or planning. The authors improved an open-source solver called HiGHS by adding four methods that try to quickly find good solutions. When tested on many problems, the improved solver found good answers faster and solved a few more cases. Two of the four methods did not end up helping in full runs but were kept as part of the system.
What this means in practice
- •For operations research teams: Improve solving speed and solution quality for scheduling and planning problems using the enhanced HiGHS solver.
- •For supply chain analysts: Use the updated HiGHS to find feasible mixed-integer solutions faster for logistics and resource allocation challenges.
Authors
Simon Spoorendonk
Abstract
We present reference implementations of four published primal heuristics for mixed-integer programming inside the open-source solver HiGHS (Huangfu and Hall, 2018): Feasibility Jump (Luteberget and Sartor, 2023), fix-propagate-repair (FPR; Salvagnin, Roberti and Fischetti, 2025) with its LP-guided dive-time variant, LocalMIP (Lin, Zou and Cai, 2024), and the first-order-LP feasibility pump Scylla (Mexi et al., 2025). They share one integration interface with per-heuristic budgets and patiences, and each runs in parallel on independently seeded workers. The evaluation is on the mipfeas benchmark (Bussieck and Dirkse, 2026), 233 instances at 600 s, against a separately built unpatched HiGHS on the same machine. The primal integral improves by 23.7% over the full set and by 12.9% on the instances not used for tuning: the patched solver reaches a good solution sooner. At the time limit it is slightly ahead. It finds a solution on 4 instances where the unpatched solver finds none, against 1 the other way, and its final gap is smaller, significantly so only over the full set. Scylla and the LP-guided dive produced no accepted incumbent in any full-limit run that carried them and ship disabled; their implementations remain. The implementation is released as open source.