Presolve heuristics in HiGHS: implementation and computational study
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.
Related
- Cohen-Lenstra heuristics and vanishing of zeta functions for superelliptic curves over finite fields
- On the notion of reasonable functions in Cohen--Lenstra type heuristics
- Fix-and-propagate heuristics using low-precision first-order LP solutions for large-scale mixed-integer linear optimization
- Hyper-Heuristics and Scheduling Problems: Strategies, Application Areas, and Performance Metrics
- Theoretical Foundations of Computational Islamic Jurisprudence (Fiqh)
BibTeX
@misc{spoorendonk2026presolve,
title = {{Presolve heuristics in HiGHS: implementation and computational study}},
author = {Simon Spoorendonk},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.22938},
eprint = {2609.22938},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.22938},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Presolve heuristics in HiGHS: implementation and computational study
AU - Simon Spoorendonk
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2609.22938
UR - https://arxiv.org/abs/2609.22938
AB - 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.
ER -