CS Paper Radar

Presolve heuristics in HiGHS: implementation and computational study

Simon Spoorendonk

cs.MS math.OC ·submitted 2026-09-19 10:29 UTC · v1
benchmarkcode/data

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Race, Exchange, Improve: Finding high-quality MIP solutions quickly

cs.DC math.OC ·2026-09-05 ·Gioni Mexi, Daniel Rehfeldt
benchmarkcode/data similarity 0.63
Abstract · 10 pages, 2 figures, 3 tables

Mixed-integer programming (MIP) is a cornerstone in applied optimization, both in industry and academia. Recently, there has been increased attention to finding strong primal solutions quickly. This is reflected, for example, in the development of the NVIDIA cuOpt solver and, most recently, in the new MIPFEAS benchmark, which has a tight time limit of 600 seconds and evaluates solvers based on how quickly they find high-quality primal solutions. This article introduces a MIP portfolio parallelization scheme, focusing on efficiently exchanging information between its workers. We present two implementations of this scheme: one built directly into the open-source MIP solver SCIP, and an external one, which we call ReXi. ReXi is currently the fastest non-commercial solver in the MIPFEAS benchmark, followed by the SCIP-integrated implementation. Moreover, we present new versions of both implementations that considerably outperform their predecessors on the MIPFEAS benchmark.

0.61

PaNGEA: Parallel Node Generation and Exploration Algorithm on GPU

cs.DC math.OC ·2026-10-02 ·Jean Pauphilet, Yupeng Wu
similarity 0.62
Abstract

Primal heuristics for finding high-quality feasible solutions are an important component in mixed-integer optimization (MIO) solvers. Recent advances in GPU-accelerated optimization algorithms show the potential of GPU acceleration for continuous optimization. In this paper, we introduce the Parallel Node Generation and Exploration Algorithm (PaNGEA), a GPU-friendly MIO primal heuristic. PaNGEA explores restricted subproblems by combining linear-relaxation solves with a local-search procedure designed for efficient batched execution on GPUs. In addition, instead of relying on a single heuristic for iterative variable fixing, we leverage GPU batching capabilities to generate and explore multiple subproblems in parallel. PaNGEA leverages GPU capabilities in two ways. First, on 283 MIPcc26 and MIPLIB instances, implementing a single-node primal heuristic on the GPU reduces the average gap integral by 8-18% relative to its CPU counterpart. Second, generating and exploring multiple nodes in parallel further reduces the average gap integral by 12-19%.

0.22

Autoresearch in Mixed-Integer Linear and Nonlinear Programming

cs.AI ·2026-09-30 ·Yuwei Gu, Yaoxin Wu, Tong Guo, Wen Song, Zhiguang Cao
benchmark similarity 0.62
Abstract

Despite recent progress in autoresearch, applying it to practical operations research problems, typically formulated as NP-hard mixed-integer linear or nonlinear programs (MILPs or MINLPs), remains challenging because effective research requires systematically managing competing ideas and long-horizon experimental trajectories. We introduce AutoMIP, a reusable agent skill for organizing long-horizon autoresearch in mixed-integer programming through idea pooling and algorithm tree search. AutoMIP maintains a persistent pool of complementary candidate ideas while organizing executable experiments into an algorithm tree, enabling the agent to preserve unexplored hypotheses, refine promising algorithms, and switch to alternative methodological directions based on historical states. On MILP and MINLP benchmark cohorts, AutoMIP achieves the highest final success rates among the evaluated autoresearch frameworks. On MIPLib, AutoMIP discovers new best solutions for 31 of 60 instances, surpassing existing autoresearch frameworks. On MINLPLib, it achieves new best solutions for 52 of 60 instances. Ablation studies further demonstrate the complementary contributions of idea pooling and algorithm tree search, highlighting the importance of jointly maintaining diverse research ideas and structured experimental trajectories for long-horizon autoresearch.

0.27

Agent-written heuristics versus commercial solvers on unsolved job-shop benchmark instances

cs.AI math.OC ·2026-11-13 ·Andre Albrecht, Enzo Morosini Frazzon, Leandro C. Coelho, Bruno Vieira
benchmarktheorycode/data similarity 0.60
Abstract · 27 pages, 4 figures, 14 tables. Submitted to International Transactions in Operational Research. Data, schedules, checkers and code: https:/…

Commercial solvers are the standard tool for difficult scheduling problems. We study whether a frontier large language model, used as a coding agent with open-source tools only, can match them in quality and speed. We report every run, and independent checkers verify every schedule. On the 100,000-operation job shop tai_100_1000_1, an agent-written solver reached 525,515, below OptalCP, Hexaly, and CP Optimizer. Unchanged, it improved all ten instances of the family and closed two. With equal budgets on the same workstation, it ended 0.0-1.8% above the lower bound, against 2.6-5.8% for CP Optimizer and 2.4-4.4% for Hexaly. On the Behnke-Geiger flexible job shops, an agent-written tabu search improved 11 of 32 open instances. With two transport robots, an agent-written solver improved seven of ten MKT instances. New lower bounds show that four published MKT values cannot be attained on the distributed instance files. Agent-run improvement campaigns closed eight further instances.

0.37

Fast and Accurate Hydro Unit Commitment

cs.MS math.OCeess.SY ·2026-10-29 ·Shaked Regev, Evan J. R. Brody
theory similarity 0.59
Abstract · 5 pages (Conference limit), 5 figures

We introduce a fast novel algorithm to commit hydro-generators. We show that our algorithm can commit 56 generators for 200 days 10,000 times faster than Hexaly, the leading commercial solver for scheduling problems, without sacrificing solution quality. Our method can commit 1792 generators for an entire year in approximately 20 seconds on commodity hardware. Hexaly is unable to solve problems of this size in reasonable time. We attain this runtime improvement by introducing a greedy-heuristic tailored for hydro units. We provide a direction for a possible proof that the error our solver makes decreases with the problem size. This is supported by our experimental results. We prove that our solver's runtime scales log-linearly in the number of generators and time periods.

0.51

Accelerate Bench: Evaluating Agents for Application-Level Program Optimization

cs.AI ·2026-11-16 ·Bowen Liu, Yuhan Li, Nuo Chen, Weile Luo, Miao Peng +5 more
benchmarkcode/data similarity 0.59
Abstract · 49 pages, 8 figures. Work by Bowen Liu was done during an internship at Tencent Hy Team. Yuhan Li is Project Lead; Nuo Chen is corresponding…

Application optimization requires coding agents to discover useful changes and coordinate them across a complete program while preserving the required computation. We introduce Accelerate Bench, a benchmark of 32 CPU optimization tasks adapted from scientific applications and supercomputing competitions. Each task provides a working program and specifies the workload, correctness requirements, timing boundaries, and permitted edits, leaving agents to choose where and how to optimize. Public testing supports iterative development, and a separate verifier scores the final submission. On benchmark version 1.1, we evaluate 16 coding agents, each pairing a model with a harness. Their Score@1 ranges from 25.5% to 67.4%. Most of their programs are correct, and the size of the speedup separates them: the two leading agents are at least 2x faster on 22 or more of the 32 tasks, while the other fourteen reach 2x on 8 to 17 and leave 125 of their 412 correct outcomes below 1.25x. Controlled replays show why coordination across an application matters: identical source code runs between 0.29x and 2.12x depending only on build and runtime settings, and one code change is worth 1.01x or 6.4x depending on another. Accelerate Bench pairs executable workloads with agents' programs and trajectories to evaluate both their gains and the process behind them.

0.61

Log-Driven Semantic Tuning for Mixed Integer Programming Solvers

cs.AI math.OCcs.LG ·2026-10-31 ·Zhengzhong Ricky You, Kaizhao Sun, Zeping Min, Wotao Yin, Xinshang Wang
benchmarkcode/data similarity 0.58
Abstract · 34 pages, 8 figures, 28 tables. Code and data: https://github.com/Zhengzhong-You/LDST

Automated configuration of mixed-integer programming (MIP) solvers largely relies on black-box optimization. Each trial requires an expensive solver run and provides only a scalar outcome, so tuning can require many such evaluations. Human experts take a different approach. They inspect solver logs, identify performance bottlenecks, and adjust the parameters that address them. We propose Log-Driven Semantic Tuning (LDST), which uses a large language model (LLM) to automate this process. LDST extracts compact diagnostics from solver logs, uses the LLM to propose sparse edits to the current best configuration based on parameter meanings and observed solver behavior, and validates each proposal before execution. A regime-adaptive objective selects the tuning signal according to the information available from a time-limited run, while a log-based completion signal estimates completion time from branch-and-bound tree growth recorded in ordinary solver logs, so that solved and unsolved runs share one time scale. On 215 instances from five benchmark sets, LDST reduces geometric-mean loss by 43.9% on easy instances and 16.7% on intermediate instances relative to the best of SMAC3, RBFOpt, and random search. In both regimes, LDST achieves a lower loss with 10 proposals than any of these baselines achieves with 50. Configurations that LDST tunes on a single instance also transfer better than baseline configurations to unseen instances of the same family.

0.37

To Race or Not to Race? Exploiting Performance Variability in Mixed-Integer Programming via Root-Gated Resource Allocation

cs.PF math.OC ·2026-11-12 ·Mourchid Adegbindin, Brenda Dietrich, Jamol Pender
similarity 0.57
Abstract · 17 pages, 4 figures, 2 tables

Mixed-integer programming (MIP) solver runtimes vary substantially across random seeds. Parallel replication exploits this variability but can waste computational resources when applied indiscriminately. We investigate whether information from an ordinary solve can guide this allocation decision. We formulate replication under a finite deadline, establish an exact relationship between runtime dispersion and the value of independent searches, and analyze delayed replication and imperfect allocation decisions. Using 101,615 seeded SCIP runs, we examine the association between root-LP dual degeneracy and replication value. We then introduce a non-invasive root-gated policy that preserves the original solver trajectory and launches three additional seeded processes when a root dual-degeneracy indicator reaches a fixed threshold. In a prospective two-hour experiment on 130 paired instances, root-gated racing proves optimality on 77 instances (59.23%), versus 73 (56.15%) for both Single and unconditional Race-4, while reducing active worker-process occupancy by 43.00% relative to unconditional racing. These findings demonstrate the promise of selective parallel resource allocation without solver-source modifications.

0.28