# A Deep Reinforcement Learning Framework For Column Generation

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 3 Jun 2022.

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

- [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)
- [Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey](https://mlsanity.com/paper/2003.04960/) (2020)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Reinforcement Learning for Integer Programming: Learning to Cut](https://mlsanity.com/paper/1906.04859/) (2019)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing](https://mlsanity.com/paper/2010.12001/) (2020)

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

- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Rethinking the Capacity of Graph Neural Networks for Branching Strategy](https://mlsanity.com/paper/2402.07099/) (2024)
- [Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process](https://mlsanity.com/paper/2401.03244/) (2024)
- [From Large Language Models and Optimization to Decision Optimization CoPilot: A Research Manifesto](https://mlsanity.com/paper/2402.16269/) (2024)
- [ORGEval: Graph-Theoretic Evaluation of LLMs in Optimization Modeling](https://mlsanity.com/paper/2510.27610/) (2025)
- [Accelerate Presolve in Large-Scale Linear Programming via Reinforcement Learning](https://mlsanity.com/paper/2310.11845/) (2023)
- [Taking the human out of decomposition-based optimization via artificial intelligence: Part II. Learning to initialize](https://mlsanity.com/paper/2310.07082/) (2023)
- [Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems](https://mlsanity.com/paper/2310.09686/) (2023)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Learning to control inexact Benders decomposition via reinforcement learning](https://mlsanity.com/paper/2508.06700/) (2025)
- [A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation](https://mlsanity.com/paper/2312.14213/) (2023)
- [Learning to Remove Cuts in Integer Linear Programming](https://mlsanity.com/paper/2406.18781/) (2024)
- [Adaptive Stabilization Based on Machine Learning for Column Generation](https://mlsanity.com/paper/2405.11198/) (2024)
- [Accelerating data-driven algorithm selection for combinatorial partitioning problems](https://mlsanity.com/paper/2402.14332/) (2024)
- [Graph Neural Network Generalization with Gaussian Mixture Model Based Augmentation](https://mlsanity.com/paper/2411.08638/) (2024)
- [All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers](https://mlsanity.com/paper/2410.15601/) (2024)
- [Reinforcement Learning for Solving the Pricing Problem in Column Generation: Applications to Vehicle Routing](https://mlsanity.com/paper/2504.02383/) (2025)
- [Learning to Cut: Reinforcement Learning for Benders Decomposition](https://mlsanity.com/paper/2605.06516/) (2026)
- [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)
- [Machine Learning-Enhanced Ant Colony Optimization for Column Generation](https://mlsanity.com/paper/2407.01546/) (2024)
- [A Neural Network Framework for Discovering Closed-form Solutions to Quadratic Programs with Linear Constraints](https://mlsanity.com/paper/2510.23737/) (2025)
- [Predictive Dual Smoothing for Column Generation](https://mlsanity.com/paper/2609.34740/) (2026)

## Abstract (arXiv)

Column Generation (CG) is an iterative algorithm for solving linear programs (LPs) with an extremely large number of variables (columns). CG is the workhorse for tackling large-scale textitinteger linear programs, which rely on CG to solve LP relaxations within a branch and price algorithm. Two canonical applications are the Cutting Stock Problem (CSP) and Vehicle Routing Problem with Time Windows (VRPTW). In VRPTW, for example, each binary variable represents the decision to include or exclude a textitroute, of which there are exponentially many; CG incrementally grows the subset of columns being used, ultimately converging to an optimal solution. We propose RLCG, the first Reinforcement Learning (RL) approach for CG. Unlike typical column selection rules which myopically select a column based on local information at each iteration, we treat CG as a sequential decision-making problem: the column selected in a given iteration affects subsequent column selections. This perspective lends itself to a Deep Reinforcement Learning approach that uses Graph Neural Networks (GNNs) to represent the variable-constraint structure in the LP of interest. We perform an extensive set of experiments using the publicly available BPPLIB benchmark for CSP and Solomon benchmark for VRPTW. RLCG converges faster and reduces the number of CG iterations by 22.4% for CSP and 40.9% for VRPTW on average compared to a commonly used greedy policy. Our code is available at https://github.com/chichengmessi/reinforcement-learning-for-column-generation.git.