  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 \textit{integer} 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 \textit{route}, 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.
