# Differentiable Combinatorial Scheduling at Scale

arXiv: https://arxiv.org/abs/2406.06593 · HTML: https://mlsanity.com/paper/2406.06593/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 67 references that are in the map.
- First posted on arXiv 6 Jun 2024.

## Builds on (most cited first, 18 of 18)

- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [In-Datacenter Performance Analysis of a Tensor Processing Unit](https://mlsanity.com/paper/1704.04760/) (2017)
- [XLS-R: Self-supervised Cross-lingual Speech Representation Learning at Scale](https://mlsanity.com/paper/2111.09296/) (2021)
- [FBNet: Hardware-Aware Efficient ConvNet Design via Differentiable Neural Architecture Search](https://mlsanity.com/paper/1812.03443/) (2018)
- [vq-wav2vec: Self-Supervised Learning of Discrete Speech Representations](https://mlsanity.com/paper/1910.05453/) (2019)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Mixed Precision Quantization of ConvNets via Differentiable Neural Architecture Search](https://mlsanity.com/paper/1812.00090/) (2018)
- [MiLeNAS: Efficient Neural Architecture Search via Mixed-Level Reformulation](https://mlsanity.com/paper/2003.12238/) (2020)
- [Developing Synthesis Flows Without Human Knowledge](https://mlsanity.com/paper/1804.05714/) (2018)
- [Ordering Chaos: Memory-Aware Scheduling of Irregularly Wired Neural Networks for Edge Devices](https://mlsanity.com/paper/2003.02369/) (2020)
- [Gamora: Graph Learning based Symbolic Reasoning for Large-Scale Boolean Networks](https://mlsanity.com/paper/2303.08256/) (2023)
- [Auto-NBA: Efficient and Effective Search Over the Joint Space of Networks, Bitwidths, and Accelerators](https://mlsanity.com/paper/2106.06575/) (2021)
- [RESPECT: Reinforcement Learning based Edge Scheduling on Pipelined Coral Edge TPUs](https://mlsanity.com/paper/2304.04716/) (2023)
- [Standard Cell Library Design and Optimization Methodology for ASAP7 PDK](https://mlsanity.com/paper/1807.11396/) (2018)
- [Accelerating Exact Combinatorial Optimization via RL-based Initialization -- A Case Study in Scheduling](https://mlsanity.com/paper/2308.11652/) (2023)
- [A3C-S: Automated Agent Accelerator Co-Search towards Efficient Deep Reinforcement Learning](https://mlsanity.com/paper/2106.06577/) (2021)
- [GATSPI: GPU Accelerated Gate-Level Simulation for Power Improvement](https://mlsanity.com/paper/2203.06117/) (2022)

## Built on by (most cited first, 6 of 6)

- [HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization](https://mlsanity.com/paper/2506.07972/) (2025)
- [e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving](https://mlsanity.com/paper/2508.13020/) (2025)
- [JigsawComm: Joint Semantic Feature Encoding and Transmission for Communication-Efficient Cooperative Perception](https://mlsanity.com/paper/2511.17843/) (2025)
- [Dataless Neural Networks for Resource-Constrained Project Scheduling](https://mlsanity.com/paper/2507.05322/) (2025)
- [GauS: Differentiable Scheduling Optimization via Gaussian Reparameterization](https://mlsanity.com/paper/2602.20427/) (2026)
- [Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling](https://mlsanity.com/paper/2603.28943/) (2026)

## Abstract (arXiv)

This paper addresses the complex issue of resource-constrained scheduling, an NP-hard problem that spans critical areas including chip design and high-performance computing. Traditional scheduling methods often stumble over scalability and applicability challenges. We propose a novel approach using a differentiable combinatorial scheduling framework, utilizing Gumbel-Softmax differentiable sampling technique. This new technical allows for a fully differentiable formulation of linear programming (LP) based scheduling, extending its application to a broader range of LP formulations. To encode inequality constraints for scheduling tasks, we introduce textitconstrained Gumbel Trick, which adeptly encodes arbitrary inequality constraints. Consequently, our method facilitates an efficient and scalable scheduling via gradient descent without the need for training data. Comparative evaluations on both synthetic and real-world benchmarks highlight our capability to significantly improve the optimization efficiency of scheduling, surpassing state-of-the-art solutions offered by commercial and open-source solvers such as CPLEX, Gurobi, and CP-SAT in the majority of the designs.