# Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 43 references that are in the map.
- First posted on arXiv 8 Dec 2021.

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

- [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)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Generalization of Machine Learning for Problem Reduction: A Case Study on Travelling Salesman Problems](https://mlsanity.com/paper/2005.05847/) (2020)
- [DASH: Dynamic Approach for Switching Heuristics](https://mlsanity.com/paper/1307.4689/) (2013)

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

- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation](https://mlsanity.com/paper/2312.14213/) (2023)
- [Adaptive Stabilization Based on Machine Learning for Column Generation](https://mlsanity.com/paper/2405.11198/) (2024)
- [Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks](https://mlsanity.com/paper/2310.07979/) (2023)
- [Enhancing Constraint Programming via Supervised Learning for Job Shop Scheduling](https://mlsanity.com/paper/2211.14492/) (2022)
- [Boosting Column Generation with Graph Neural Networks for Joint Rider Trip Planning and Crew Shift Scheduling](https://mlsanity.com/paper/2401.03692/) (2024)
- [All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers](https://mlsanity.com/paper/2410.15601/) (2024)
- [A Neural Column Generation Approach to the Vehicle Routing Problem with Two-Dimensional Loading and Last-In-First-Out Constraints](https://mlsanity.com/paper/2406.12454/) (2024)
- [A Neural Network Framework for Discovering Closed-form Solutions to Quadratic Programs with Linear Constraints](https://mlsanity.com/paper/2510.23737/) (2025)
- [Imitation Learning for Combinatorial Optimisation under Uncertainty](https://mlsanity.com/paper/2601.05383/) (2026)
- [Predictive Dual Smoothing for Column Generation](https://mlsanity.com/paper/2609.34740/) (2026)

## Abstract (arXiv)

Column Generation (CG) is an effective method for solving large-scale optimization problems. CG starts by solving a sub-problem with a subset of columns (i.e., variables) and gradually includes new columns that can improve the solution of the current subproblem. The new columns are generated as needed by repeatedly solving a pricing problem, which is often NP-hard and is a bottleneck of the CG approach. To tackle this, we propose a Machine-Learning-based Pricing Heuristic (MLPH)that can generate many high-quality columns efficiently. In each iteration of CG, our MLPH leverages an ML model to predict the optimal solution of the pricing problem, which is then used to guide a sampling method to efficiently generate multiple high-quality columns. Using the graph coloring problem, we empirically show that MLPH significantly enhancesCG as compared to six state-of-the-art methods, and the improvement in CG can lead to substantially better performance of the branch-and-price exact method.