arXiv preprint ·
To Race or Not to Race? Exploiting Performance Variability in Mixed-Integer Programming via Root-Gated Resource Allocation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Snoopie: A Multi-GPU Communication Profiler and Visualizer
TIDE: Reclaiming Lost Performance In On-Policy Reinforcement Learning
SPEC CPU2026 Under the Microscope: Programs, Phases, and Samples
PerfArena: Ranking LLMs by Code Performance
Beyond Blossom: Accelerating MWPM Decoding for Surface Codes With Local Predecoding and Architecture-Aware Optimizations
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.