Research map / Learning theory and algorithms / Combinatorial and search optimization
Differentiable Combinatorial Scheduling at Scale
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a differentiable SDC-based scheduler using Gumbel-Softmax and a constrained Gumbel trick, optimized by gradient descent without training data, outperforming CPLEX, Gurobi and CP-SAT on EPFL-derived and random scheduling workloads.
Problem
Latency-constrained min-resource scheduling of dataflow graphs (NP-hard), e.g. GPU circuit simulation workloads, where exact ILP/CP solvers scale poorly and heuristics are suboptimal.
Approach
Vectorize SDC schedule variables as one-hot stage distributions, enforce difference constraints via a cumsum-based transformation (T_≤) inside the Gumbel-Softmax sampling ("constrained Gumbel Trick"), and optimize entropy-based memory and communication losses by gradient descent on GPU without training data.
Key results
- Method converges within the first 360 seconds on dense and sparse random workloads, while CPLEX and Gurobi barely start optimizing denser workloads.
- On the largest EPFL designs (Square, Voter), CPLEX and Gurobi barely initiate optimization within the 3600 s timeout whereas the proposed method reaches good solutions within 360 s.
- Authors acknowledge the method underperforms commercial/CP-SAT solvers on some smaller or sparser designs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use differentiable scheduling with constrained Gumbel sampling instead of CPLEX or Gurobi | Differentiable scheduling · Synthetic random workloads | optimization convergence speed | Helped |
| Use differentiable scheduling instead of CPLEX or Gurobi | Differentiable scheduling · Large EPFL designs | optimization convergence speed | Helped |
| Use differentiable scheduling instead of CP-SAT | Differentiable scheduling · Large or dense synthetic workloads | optimization success | Helped |
| Use differentiable scheduling instead of CP-SAT | Differentiable scheduling · EPFL designs | optimization success | Helped |
| Use differentiable scheduling on smaller or sparse designs | Differentiable scheduling · Small-scale or sparse scheduling problems | optimization quality | Hurt |
| Switch from Adam to AdamW | Differentiable scheduling · Selected synthetic workloads and EPFL designs | loss convergence | No clear effect |
Surprising findings
- CP-SAT outperforms the proposed method on some small, sparse designs, and the method offers little advantage on trivial problems.
- Loss curves show overfitting beyond certain epochs, limiting objective optimization.
Limitations
- Quality falls short of CPLEX, Gurobi and CP-SAT on smaller or sparse designs
- Advantage is small on trivial problems; benefit grows with graph density
- Overfitting in loss convergence beyond certain epochs
Experimental setup
Datasets: EPFL benchmark suite (derived GPU computational graphs) synthetic random workloads RW1-RW12
Benchmarks: EPFL benchmark designs (Adder, Barrel shifter, i2c controller, Max, Square, Voter, and mapped variants) synthetic random workloads RW1-RW12
Metrics: normalized objective value vs. runtime (360s intervals, 3600 loss convergence
Baselines: CPLEX Gurobi CP-SAT
Builds on: Gumbel-Softmax system of difference constraints (SDC) scheduling Gumbel-Max trick
Closest papers by meaning
- GauS: Differentiable Scheduling Optimization via Gaussian Reparameterization (NeurIPS 2026 · similarity 0.87)
- Optimistic Tree Searches for Combinatorial Black-Box Optimization (NeurIPS 2022 · similarity 0.84)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.84)
- Accelerating Optimization via Differentiable Stopping Time (NeurIPS 2025 · similarity 0.83)
- B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints (NeurIPS 2026 · similarity 0.83)
- Differentiable extensions with rounding guarantees for combinatorial optimization over permutations (NeurIPS 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.