Search papers, labs, and topics across Lattice.
This paper introduces a hybrid CPU-GPU framework for combinatorial scheduling problems by using differentiable presolving to generate warm-start solutions for ILP solvers. Differentiable optimization rapidly produces high-quality partial solutions, enabling improved early pruning compared to standalone solvers. Empirical results on industry-scale benchmarks show up to a $10\times$ performance improvement and narrow the optimality gap to $<0.1\%$.
Differentiable optimization can supercharge classical ILP solvers, slashing runtime by 10x on combinatorial scheduling problems.
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.
