# Enhancing Constraint Programming via Supervised Learning for Job Shop Scheduling

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 78 references that are in the map.
- First posted on arXiv 26 Nov 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems](https://mlsanity.com/paper/2005.05847/) (2020)
- [Learning Primal Heuristics for Mixed Integer Programs](https://mlsanity.com/paper/2107.00866/) (2021)
- [Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring](https://mlsanity.com/paper/2112.04906/) (2021)
- [Learning Variable Ordering Heuristics for Solving Constraint Satisfaction Problems](https://mlsanity.com/paper/1912.10762/) (2019)
- [Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems](https://mlsanity.com/paper/1902.08455/) (2019)
- [Boosting Ant Colony Optimization via Solution Prediction and Machine Learning](https://mlsanity.com/paper/2008.04213/) (2020)

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

- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)

## Abstract (arXiv)

Constraint programming (CP) is a powerful technique for solving constraint satisfaction and optimization problems. In CP solvers, the variable ordering strategy used to select which variable to explore first in the solving process has a significant impact on solver effectiveness. To address this issue, we propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning-based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers. added[]Unlike traditional variable ordering methods, our methods can learn from the characteristics of each problem instance and customize the variable ordering strategy accordingly, leading to improved solver performance. Our experiments demonstrate that training machine learning models is highly efficient and can achieve high accuracy. Furthermore, our learned variable ordering methods perform competitively when compared to four existing methods. Finally, we demonstrate that hybridising the machine learning-based variable ordering methods with traditional domain-based methods is beneficial.