← 研踪 PaperTrailarXiv:2611.16543 · v1
To Race or Not to Race? Exploiting Performance Variability in Mixed-Integer Programming via Root-Gated Resource Allocation
首次提交 2026-11-12 17:36
版本更新 2026-11-12 17:36
雷达观测 2026-11-13 14:15
摘要
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.
作者备注：17 pages, 4 figures, 2 tables
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-12 17:36 · 最新观测版本
To Race or Not to Race? Exploiting Performance Variability in Mixed-Integer Programming via Root-Gated Resource Allocation
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.
查看此版本解读 →查看此版本原文 ↗