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× 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.
Figures & tables
Figure 1. Example of SDC-based scheduling. (Left) A DFG with three scheduling stages, having a latency of L=3 . (Right) The corresponding dependency constraints and objective functions include minimizing peak resource and inter-stage communication costs.
Figure 2. Comparison of warm-start strategies: full solution vs. partial solution. Normalized objective values are obtained at a 900s solving time. Error bars represent the range of objective values obtained when warm-starting different solvers with varying partial solutions.
Term
Definition
DiffSched
The differentiable method introduced in ( Liu et al., 2024 ) .
Cold-start
Solver execution without additional initial solutions.
Warm-start
Solver execution initialized with additional hints.
Table 1. Terminology Definitions
Design
#Constraints
T/iter (s)
Conv.
Design
#Constraints
T/iter (s)
Conv.
Adder
93066
5.38
21.03%
RW 1
102927
3.36
17.78%
Adder (M)
122930
6.68
22.96%
RW 2
105131
3.43
19.86%
Bar
264082
14.73
20.07%
RW 3
104071
5.07
16.72%
Bar (M)
239166
11.07
20.60%
RW 4
36641
1.22
16.31%
i2c
114124
6.51
18.75%
RW 5
38213
1.27
16.94%
i2c (M)
96182
5.01
17.63%
RW 6
41267
2.60
16.98%
Table 2. Benchmark Details. #Constraints: ILP formulation constraint count; T/iter: DiffSched runtime per iteration; Conv.: converged objective value of DiffSched .
Figure 3. Confidence analysis: Left: Aggregated confidence distributions with the top 30% region shaded. Right: Average confidence for the top 30% assignments across 30 iterations. Rows correspond to RW, EPFL, and mapped EPFL designs.
Figure 4. Performance comparison across 24 benchmark instances, sorted by ILP constraint count (small to large). Cold-start/Warm-start results are collected at 3600s/1800s, respectively. Lower objective value indicates better performance.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
Efficient operator scheduling is a fundamental challenge in software compilation and hardware synthesis. While recent differentiable approaches have sought to replace traditional ones like exact solvers or heuristics with gradient-based search, they typically rely on categorical distributions that fail to capture the ordinal nature of time and suffer from a parameter space that scales poorly. In this paper, we propose a novel differentiable framework, GauS, that models operator scheduling as a stochastic relaxation using Gaussian distributions, which fully utilize modern parallel computing devices like GPUs. By representing schedules as continuous Gaussian variables, we successfully capture the ordinal nature of time and reduce the optimization space by orders of magnitude. Our method is highly flexible to represent various objectives and constraints, which provides the first differentiable formulation for the complex pipelined scheduling problem. We evaluate our method on a range of benchmarks, demonstrating that Gaus achieves Pareto-optimal results.
Yaohui Cai, Vesal Bakhtazad, Cunxi Yu +1
Cornell University · University of Maryland, College Park
Dynamic Programming (DP) and Constraint Programming (CP) are well-established paradigms for solving combinatorial optimization problems. Usually, these two approaches are used separately. This paper aims to show that the two can be combined effectively and elegantly, with DP serving as the primary search framework and CP used as a subroutine to leverage global constraint propagation. This paper presents such an approach for the Partial Shop Scheduling Problem (PSSP), for which a pure DP method has previously been proposed, and efficient CP filtering algorithms are available. The PSSP is a general scheduling problem where each job consists of a set of operations with arbitrary precedence constraints. The approach is flexible enough to accommodate anytime DP strategies, such as anytime column search, whereas the original DP algorithm operated in a strictly layer-wise manner. Moreover, the flexibility of the CP modeling makes it straightforward to incorporate arbitrary precedence constraints. As a result, the model naturally handles any precedence graph and even enables the design of a Large Neighborhood Search (LNS) scheme, in which the DP model is reused, and partial-order schedules are imposed across restarts to improve the incumbent solution. While not competitive with state-of-the-art pure CP solvers for this specific problem, our primary contribution is demonstrating the viability of this hybrid integration.
Combinatorial optimization problems arise in logistics, scheduling, and resource allocation, yet existing approaches face a fundamental trade-off among generality, performance, and usability. We present cuGenOpt, a GPU-accelerated general-purpose metaheuristic framework that addresses all three dimensions simultaneously. At the engine level, cuGenOpt adopts a "one block evolves one solution" CUDA architecture with a unified encoding abstraction (permutation, binary, integer), a two-level adaptive operator selection mechanism, and hardware-aware resource management. At the extensibility level, a user-defined operator registration interface allows domain experts to inject problem-specific CUDA search operators. At the usability level, a JIT compilation pipeline exposes the framework as a pure-Python API, and an LLM-based modeling assistant converts natural-language problem descriptions into executable solver code. Experiments across five thematic suites on three GPU architectures (T4, V100, A800) show that cuGenOpt outperforms general MIP solvers by orders of magnitude, achieves competitive quality against specialized solvers on instances up to n=150, and attains 4.73% gap on TSP-442 within 30s. Twelve problem types spanning five encoding variants are solved to optimality. Framework-level optimizations cumulatively reduce pcb442 gap from 36% to 4.73% and boost VRPTW throughput by 75-81%. Code: https://github.com/L-yang-yang/cugenopt