# Adaptive Stabilization Based on Machine Learning for Column Generation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 55 references that are in the map.
- First posted on arXiv 18 May 2024.

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

- [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)
- [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)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning](https://mlsanity.com/paper/2302.01578/) (2023)
- [Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness](https://mlsanity.com/paper/2110.10942/) (2021)
- [A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2106.04927/) (2021)
- [A Deep Reinforcement Learning Framework For Column Generation](https://mlsanity.com/paper/2206.02568/) (2022)
- [Machine Learning for Cutting Planes in Integer Programming: A Survey](https://mlsanity.com/paper/2302.09166/) (2023)
- [Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method](https://mlsanity.com/paper/2110.06365/) (2021)
- [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)
- [Boosting Ant Colony Optimization via Solution Prediction and Machine Learning](https://mlsanity.com/paper/2008.04213/) (2020)

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

- [Partial Column Generation with Graph Neural Networks for Team Formation and Routing](https://mlsanity.com/paper/2509.15275/) (2025)
- [Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation](https://mlsanity.com/paper/2607.13373/) (2026)
- [Predictive Dual Smoothing for Column Generation](https://mlsanity.com/paper/2609.34740/) (2026)
- [Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut](https://mlsanity.com/paper/2610.21001/) (2026)

## Abstract (arXiv)

Column generation (CG) is a well-established method for solving large-scale linear programs. It involves iteratively optimizing a subproblem containing a subset of columns and using its dual solution to generate new columns with negative reduced costs. This process continues until the dual values converge to the optimal dual solution to the original problem. A natural phenomenon in CG is the heavy oscillation of the dual values during iterations, which can lead to a substantial slowdown in the convergence rate. Stabilization techniques are devised to accelerate the convergence of dual values by using information beyond the state of the current subproblem. However, there remains a significant gap in obtaining more accurate dual values at an earlier stage. To further narrow this gap, this paper introduces a novel approach consisting of 1) a machine learning approach for accurate prediction of optimal dual solutions and 2) an adaptive stabilization technique that effectively capitalizes on accurate predictions. On the graph coloring problem, we show that our method achieves a significantly improved convergence rate compared to traditional methods.