用可微分方法加速大规模调度求解，性能提升10倍。
Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling
- 用可微分预处理快速生成优质部分解，作为精确求解器的起点。
- 在工业级基准上实现最高10倍性能提升，最优性差距小于0.1%。
- 首次将机器学习初始化引入精确整数规划求解，适合优化工程人群。
本文提出一种混合CPU-GPU框架，用于求解以整数线性规划（ILP）形式建模的组合调度问题。尽管调度支撑计算系统中诸多优化任务，但因问题为NP-hard，在大规模下实现最优解仍是长期挑战。我们提出一种新方法，将可微分优化与经典ILP求解结合：利用可微分预处理快速生成高质量部分解，作为商业求解器（CPLEX、Gurobi）和新兴开源求解器HiGHS的热启动。该方法显著提升早期剪枝效率，相比现有独立求解器表现更优。在工业级基准上的实验表明，性能最高提升10倍，最优性差距缩窄至<0.1%。本工作首次展示将可微分优化用于初始化精确ILP求解器解决组合调度问题，为机器学习基础设施与经典精确优化方法的融合开辟新路径。
原文摘要 · Abstract (English)
This paper presents a hybrid CPU-GPU framework for solving combinatorial scheduling problems formulated as Integer Linear Programming (ILP). While scheduling underpins many optimization tasks in computing systems, solving these problems optimally at scale remains a long-standing challenge due to their NP-hard nature. We introduce a novel approach that combines differentiable optimization with classical ILP solving. Specifically, we utilize differentiable presolving to rapidly generate high-quality partial solutions, which serve as warm-starts for commercial ILP solvers (CPLEX, Gurobi) and rising open-source solver HiGHS. This method enables significantly improved early pruning compared to state-of-the-art standalone solvers. Empirical results across industry-scale benchmarks demonstrate up to a $10\times$ performance gain over baselines, narrowing the optimality gap to $<0.1\%$. This work represents the first demonstration of utilizing differentiable optimization to initialize exact ILP solvers for combinatorial scheduling, opening new opportunities to integrate machine learning infrastructure with classical exact optimization methods across broader domains.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。