Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling DOI: XXXXXXX.XXXXXXX Conference: ACM/IEEE International Symposium on Machine Learning for CAD; September 7–9, 2026; Jeju Island, South Korea

Mingju Liu, Jiaqi Yin, Alvaro Velasquez, Cunxi Yu · 2026

Read Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling DOI: XXXXXXX.XXXXXXX Conference: ACM/IEEE International Symposium on Machine Learning for CAD; September 7–9, 2026; Jeju Island, South Korea by Mingju Liu, Jiaqi Yin, Alvaro Velasquez, Cunxi Yu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-28943.txt.

Introduction

Liu and co-authors present a CPU-GPU hybrid method for combinatorial scheduling cast as integer linear programming. Such problems are NP-hard, so optimal solving at scale is hard. Their method uses differentiable presolving to make partial solutions fast. Those partial solutions warm start exact solvers like CPLEX, Gurobi, and HiGHS. Early pruning improves a lot over standalone solvers. On industry scale benchmarks, gains reached tenfold, and the optimality gap fell below 0.1 percent. It is a first show of such methods seeding exact solvers.

Catalog record

CREATORMingju Liu, Jiaqi Yin, Alvaro Velasquez, Cunxi Yu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34357
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.28943

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling DOI: XXXXXXX.XXXXXXX Conference: ACM/IEEE International Symposium on Machine Learning for CAD; September 7–9, 2026; Jeju Island, South Korea Mingju Liu, Jiaqi Yin, Alvaro Velasquez, Cunxi Yu Abstract . 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 × 10\times performance gain over baselines, narrowing the optimality gap to < 0.1 % <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. 1. Introduction Combinatorial scheduling lies at the core of many optimization problems in computing systems, where the goal is to assign tasks over time and resources under dependency and capacity constraints. It plays a pivotal role in domains such as hardware synthesis, where efficient scheduling directly impacts performance, area, and power consumption. However, the problem is NP-hard , and designing scalable and optimal solutions remains a long-standing challenge. One of the most successful formulations of scheduling problems uses System of Difference Constraints (SDC) , a subclass of the more general Integer Linear Programming (ILP) systems. In these systems, each linear constraint involves at most two variables (e.g., x_{i}-x_{j}\leq b ), which compactly captures task dependencies and timing/resource constraints ( 8 ; 9 ) . These constraints can be directly encoded in ILP, enabling the derivation of provably optimal schedules. This method has been widely adopted in commercial and industrial tools such as AMD Xilinx Vivado/Vitis HLS ( 19 ; 7 ) and Google’s XLS ( 3 ) . Despite the advantage of optimality, ILP-based methods suffer from limited scalability due to exponential computational complexity and reliance on general-purpose solvers. To address this, heuristic algorithms such as ( 23 ; 5 ; 1 ) have been developed to provide fast, often problem-specific solutions that sacrifice optimality for runtime efficiency. More recently, machine learning (ML) techniques are explored to overcome limitations of exact and heuristic methods by leveraging high-performance computing platforms like GPUs ( 24 ) and TPUs ( 17 ) . These techniques broadly fall into three categories: • Imitation Learning (IL) ( 4 ; 11 ; 10 ; 25 ; 13 ) : These approaches learn policies from expert demonstrations or optimal solutions. While effective in constrained scenarios, they struggle with generalization due to limited data diversity and domain shift. • Reinforcement Learning (RL) ( 21 ; 18 ; 6 ; 28 ; 29 ; 30 ; 22 ) : RL learns directly from interaction and reward signals, enabling the discovery of novel scheduling strategies. However, it often suffers from large runtime overhead and unstable convergence in large-scale problems. • Differentiable Optimization The recent state-of-the-art (SOTA) differentiable optimization framework ( 20 ) has emerged that forms a combinatorial scheduling problem using stochastic relaxation and gradient-based optimization. Built upon the Gumbel-Softmax ( 16 ) , this method enables training-free, dataless optimization with customizable objectives. While it demonstrates fast convergence and competitive results on large benchmarks, it still yields sub-optimal schedules due to non-convexity and approximation inherent in the relaxation. In this work, we propose a novel combinatorial scheduling framework that integrates SDC/ILP formulations with differentiable optimization to provide a hybrid CPU-GPU solution balancing both optimality and scalability . Specifically, we introduce a two-stage hybrid scheduling flow that leverages differentiable optimization to address the sub-optimality of pure gradient-based methods, while simultaneously accelerating ILP solving. The key novelty of this work lies in using differentiable optimization—via gradient-descent algorithms—as a differentiable warm-start for exact ILP solvers, which aims to bring a seamless integration between machine learning infrastructure into exact ILP solving. Default ILP pre-solving techniques often rely on heuristics or prior feasible solutions, which are difficult to generate for complex scheduling instances due to significant runtime consumption and offer limited coverage of the solution space. As demonstrated in our experimental results compared to SOTA commercial tools with all warm-start options enabled, our method uses a differentiable relaxation based on the constrained Gumbel Trick to rapidly explore feasible regions and generate high-quality partial solutions. These solutions are then used to warm-start SOTA ILP solvers, enabling faster convergence to optimal or near-optimal schedules. To the best of our knowledge, this is the first approach that leverages differentiable optimization as an initialization mechanism to accelerate exact ILP solvers for combinatorial scheduling problems and offers new opportunities in CPU-GPU hybrid combinatorial optimization. Our methodology, built on SDC constraints, comprises: (1) fast differentiable optimization with on-the-fly, confidence-based partial solution selection, and (2) warm-starting commercial and open-source SOTA ILP solvers such as CPLEX ( 15 ) , Gurobi ( 12 ) , and HiGHS ( 14 ) . This hybrid flow achieves significantly improved scheduling performance by combining the efficiency of CPU-GPU accelerated differentiable solvers with the robustness of ILP-based exact methods. Our experiment results demonstrate significant improvements over SOTAs, while more importantly maintaining the optimality and determinism guarantees. This differentiable warm-start two-stage hybrid optimization workflow provides the potential to be extended beyond combinatorial scheduling to general ILP problems. Our code and setups will be open-sourced. 2. Preliminary 2.1. Scheduling and Problem statement Scheduling is a well-established combinatorial challenge with extensive real-world relevance. In this work, we schedule tasks in a dataflow graph modeled as a directed acyclic graph (DAG) G(V,E) , where each node v\in V represents a computational task and each edge e\in E encodes a data dependency between graph nodes. In many settings, cost metrics are assigned to nodes and/or edges in the form of weights. Additionally, various constraints—such as timing requirements or limitations on available resources—may be imposed depending on the specific scheduling scenario. We define a schedule \mathbf{S}=(s_{0},s_{1},\ldots,s_{i}) , where s_{i} denotes the stage in which node v_{i} is executed. Under a given latency L , representing the maximum completion time of the entire DAG, the objective is to minimize resource usage (and/or other specified costs) while respecting all dependency constraints. This formulation is referred to as a latency-constrained min-resource scheduling problem. Various approaches have been explored to address combinatorial scheduling challenges in compiler optimization and hardware synthesis. Machine learning (ML) techniques, particularly Topoformer ( 10 ) , introduce attention-based graph neural networks for topological ordering through node embedding learning. ( 13 ) combines ML with optimization and proposes a novel predict-and-search framework for efficiently identifying high-quality feasible solutions. While promising, such supervised learning approaches face limitations in generalizability and data dependency. Reinforcement learning (RL) with graph learning-based schedulers ( 6 ; 28 ; 29 ) attempts to address these limitations by learning from action rewards, though challenges persist in scalability and training overhead. 2.2. SDC and Related Methods Figure 1 . Example of SDC-based scheduling. (Left) A

Read the complete text