# Accelerating Exact Combinatorial Optimization via RL-based Initialization -- A Case Study in Scheduling

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 38 references that are in the map.
- First posted on arXiv 19 Aug 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Xception: Deep Learning with Depthwise Separable Convolutions](https://mlsanity.com/paper/1610.02357/) (2016)
- [Identity Mappings in Deep Residual Networks](https://mlsanity.com/paper/1603.05027/) (2016)
- [Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning](https://mlsanity.com/paper/1602.07261/) (2016)
- [In-Datacenter Performance Analysis of a Tensor Processing Unit](https://mlsanity.com/paper/1704.04760/) (2017)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Learning Scheduling Algorithms for Data Processing Clusters](https://mlsanity.com/paper/1810.01963/) (2018)
- [Machine Learning for Electronic Design Automation: A Survey](https://mlsanity.com/paper/2102.03357/) (2021)
- [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)
- [Painting on Placement: Forecasting Routing Congestion using Conditional Generative Adversarial Nets](https://mlsanity.com/paper/1904.07077/) (2019)
- [Mitigating Edge Machine Learning Inference Bottlenecks: An Empirical Study on Accelerating Google Edge Models](https://mlsanity.com/paper/2103.00768/) (2021)
- [RESPECT: Reinforcement Learning based Edge Scheduling on Pipelined Coral Edge TPUs](https://mlsanity.com/paper/2304.04716/) (2023)

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

- [Differentiable Combinatorial Scheduling at Scale](https://mlsanity.com/paper/2406.06593/) (2024)
- [Verilog-to-PyG -- A Framework for Graph Learning and Augmentation on RTL Designs](https://mlsanity.com/paper/2311.05722/) (2023)
- [e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving](https://mlsanity.com/paper/2508.13020/) (2025)
- [Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling](https://mlsanity.com/paper/2603.28943/) (2026)

## Abstract (arXiv)

Scheduling on dataflow graphs (also known as computation graphs) is an NP-hard problem. The traditional exact methods are limited by runtime complexity, while reinforcement learning (RL) and heuristic-based approaches struggle with determinism and solution quality. This research aims to develop an innovative approach that employs machine learning (ML) for addressing combinatorial optimization problems, using scheduling as a case study. The goal is to provide guarantees in optimality and determinism while maintaining the runtime cost of heuristic methods. Specifically, we introduce a novel two-phase RL-to-ILP scheduling framework, which includes three steps: 1) RL solver acts as coarse-grain scheduler, 2) solution relaxation and 3) exact solving via ILP. Our framework demonstrates the same scheduling performance compared with using exact scheduling methods while achieving up to 128 × speed improvements. This was conducted on actual EdgeTPU platforms, utilizing ImageNet DNN computation graphs as input. Additionally, the framework offers improved on-chip inference runtime and acceleration compared to the commercially available EdgeTPU compiler.