CS Paper Radar

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

Mourchid Adegbindin, Brenda Dietrich, Jamol Pender

cs.PF math.OC ·submitted 2026-11-12 09:36 UTC · v1

Abstract

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.

Comment
17 pages, 4 figures, 2 tables

Closest papers

Nearest neighbours by meaning across the whole index.

When Solvers Get Moody: Quantifying and Predicting Performance Variability in Mixed Integer Programming

cs.LG math.OC ·2026-10-09 ·Mourchid Adegbindin, Brenda Dietrich, Jamol Pender, Andrea Lodi
similarity 0.61
Abstract · 21 pages, including a 3-page electronic companion. An earlier conference version appeared in the IOS 2026 proceedings. https://doi.org/10.52…

Mixed-integer programming (MIP) solvers are widely used, yet their performance can vary substantially even under seemingly neutral perturbations. Such variability complicates benchmarking, and the interpretation of computational studies. We introduce the Weighted Variability Score (WVS), a robust multi-component metric that aggregates dispersion in normalized runtime, final optimality gap, LP iterations, and branch-and-bound nodes across repeated runs. On a large subset of MIPLIB 2017 instances, each solved in 100 randomized runs under a four-hour limit, WVS reveals a right-skewed distribution with a substantial upper tail: many instances are essentially stable, but some exhibit large variability that is not explained by basic properties alone. Notably, this experiment proved optimality for the open instance 'neos-5045105-creuse' in two SCIP runs. Using static descriptors and root-level features, a tree-based predictor with a gated tail uplift achieves a mean absolute error of 0.058 and Spearman rank correlation of 0.65 on a sealed test split. Feature-importance analysis highlights root degeneracy, matrix structure, coefficient ranges, and presolve reductions as the main drivers of high WVS. Because variability is systematic and partially predictable from inexpensive early-run features, our findings offer a practical tool for preemptive tuning and lay a foundation for fairer evaluation of new algorithms.

0.63

Fast and Accurate Hydro Unit Commitment

cs.MS math.OCeess.SY ·2026-10-29 ·Shaked Regev, Evan J. R. Brody
theory similarity 0.57
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

Presolve heuristics in HiGHS: implementation and computational study

cs.MS math.OC ·2026-09-19 ·Simon Spoorendonk
benchmarkcode/data similarity 0.57
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.

0.31

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

cs.DC math.OC ·2026-09-05 ·Gioni Mexi, Daniel Rehfeldt
benchmarkcode/data similarity 0.56
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

Ready Cohorts: Bounding GPU Opportunity and Avoiding Host Round Trips in LLM-Agent Control

cs.DC cs.AIcs.OS ·2026-08-12 ·Josef Liyanjun Chen
benchmarktheorycode/data similarity 0.56
Abstract · 14 pages, 4 figures. Includes formal proofs, trace provenance, and a reproducibility appendix. Code and artifacts: https://github.com/josefc…

We introduce a mechanism that improves LLM-agent execution: keeping four-byte, GPU-computed control-path routing decisions on-device, avoiding a round-trip to host memory for redispatch. It is faster than host-dispatch in all 36 placements x mechanisms settings in our benchmark across four named GPUs with row-median speedup of 1.19x-2.39x, and outputs are correct, matching an independent host implementation, for all 14,557,440 calls in all configurations, in both tested mechanisms. Agent control paths can be deterministic. Their transitions between LLM calls and external tool calls can be GPU-accelerated by batching across agents and time. We define a cohort of transitions with launch times in a window, and study four shares of GPU-active time: a fixed-partition baseline F, an optimal P*, an upper bound U, and an online result A. Under assumptions of uniform relative launch deadlines, infinite capacity, and zero service times, we compute P* with a custom dynamic program and validate our simulator against it. We replay an anonymized 851-session trace, shown in full as a panel, stationary-ized with a Poisson process. With 100,000 target active agents and a launch deadline of 50 ms, where the headline results have K=256, we find F=30.19%, P*=43.00%, U=45.85%; our method for computing P* reveals that 81.83% of this opportunity is recoverable from cohort packing at fixed window ends. Our method for U relies on a novel notion of route-key, used only as a proxy (via conditional statistics) and does not purport to establish route-equivalence. We find a nested graph that retains some host-side decisions slower in all 60 configurations (five placements).

0.30

Faster Imitation by Re-timing Demonstrations Within the Controller Limit

cs.RO cs.AI ·2026-10-31 ·Zongtan Li, Tianming Liu, Ye Zhao
similarity 0.54
Abstract · Submitted to ICRA 2027

Imitation policies inherit the operator's pace, and re-timing the demonstrations to run faster works only until success collapses at two to three times demonstration speed. Recent methods attribute that collapse to distribution shift and answer it with finer rules for which segments may be sped up; we show it has a mechanical cause that segment selection cannot address. A low-level controller realises only a bounded displacement per control period, so merging consecutive commands produces sums outside that bound: training pairs that promise a transition the plant cannot deliver. The share of such pairs in the re-timed data, which we call the exceed share, tracks where the retrained policy collapses. The rule that follows has a single parameter: merge greedily while the sum stays realisable. Every command is then realisable by construction, the demonstrated geometry is preserved, and the speed-up lands only where the demonstrator left slack. On four simulated robomimic tasks, 200 held-out seeds per cell, a merge cap of two is at or above the frozen policy's success on all four, by 14 points on Square, and shortens the successful episodes. At matched tempo, uniform re-timing loses 9 and 16 points on Can and ToolHang, is within noise on the other two, and reaches zero on the hardest at 2x. Placement also matters: no shuffled, entropy-guided or speed-conditioned alternative beats the rule on three of the four tasks, by margins the exceed share alone does not explain; on the fourth, at a tempo the task absorbs, every placement lands in the same band. The same principle carries to a simulated humanoid whole-body tracker: re-timing 429 reference motions within its velocity envelope succeeds on 71% of clips at 2.3x, against 51% for uniform time scaling at 2x.

0.13

Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study

cs.AI cs.DCcs.LG ·2026-10-08 ·Yuyu Zhang
similarity 0.54
Abstract · 19 pages, 4 figures. Preregistered negative result with an open evaluation protocol; companion artifacts archived at 10.5281/zenodo.22929494…

Monte Carlo Tree Search (MCTS) is often proposed for scheduling directed-acyclic-graph (DAG) workflows, yet most studies never run the comparison that could refute it - giving a much simpler method the same search effort. We run that comparison under a controlled protocol. All arms receive an identical budget - the same number of candidate schedules built and evaluated: an MCTS scheduling method, preregistered as the main arm; a randomized-restart list scheduler with no search tree as the control; and a textbook-UCT MCTS arm as a registered follow-up on the same domain. The analysis plan was locked before data collection; an independent checker confirmed all 768 confirmation-stage schedules valid with correct finish times. At the main budget of 2048 evaluated schedules, MCTS is 2.88% worse than the restarts (95% CI [-3.62%,-2.15%]; the 72 of 96 held-out instances with positive baseline-relative headroom). The deficit is not budget starvation: on the separate exploration pool restarts self-improve by 1.85% where MCTS gains 0.24%, and 700 of 720 of MCTS's first results are merely the warm start it was handed. The studied selection rule locks deterministically onto the first-expanded child, keeping its trials correlated while restarts draw gains from the tails; the causal link to makespan remains an inference. A structural map locates where the tree stops paying: restarts win on sparse irregular workflows, no difference is detectable on regular layered ones, and dense ones leave no room to improve. Swapping the rule for textbook UCT removes most of the deficit (-0.26%, 95% CI [-0.71%,+0.23%]) without reversing its sign. Results are confined to a controlled synthetic domain (N in {8,16,32} tasks, 2-8 processors, budgets up to 2048); we make no claim about larger budgets.

0.27

RadixFlow: Filling Execution Bubbles in Prefix-Cached Hybrid LLM Serving

cs.AI ·2026-10-13 ·Huihao Jing, Wenbin Hu, Shaojin Chen, Haochen Shi, Haoyu Huang +4 more
similarity 0.53
Abstract

Prefix reuse improves LLM inference by sharing the KV cache of common prompt prefixes. This helps only if the scheduler can execute a matched branch in the current worker round. Schedulers assume that a matched prefix is ready, which holds for full attention but fails for hybrid LLMs. There, a branch (the consumer) may need recurrent state that another branch (the producer) is still computing in the same round. The native scheduler stops its waiting-queue scan at this blocked consumer, and the resulting head-of-line blocking creates \emph{execution bubbles}: idle batch slots that independent work could fill. We introduce RadixFlow, which decouples prefix matching from state readiness. Its state-ready traversal turns a global scan barrier into a local wait: only the consumer is blocked until the next round, while feasible independent branches keep filling the batch under the native state check. On five hybrid models, RadixFlow lowers mean latency by 3\% to 24\% and worker rounds by 11\% to 44\% at almost unchanged reuse. On the larger Qwen3.5 models, ablations show that most of the gain comes from traversal, which adds little on a full-attention control. Heavier rounds limit how much of this saving reaches latency.

0.32