A Deep Reinforcement Learning Framework for Column Generation
Authors: Cheng Chi
Amine Mohamed Aboussalah
Elias Boutros Khalil
Juyoung Wang
Zoha Sherkat-Masoumi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement learning
Column Generation
Column selection
Machine learning for optimization

Abstract: 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 integer linear programs, which rely on CG to solve LP relaxations within a branch and bound 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 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, as the column selected in an iteration affects subsequent iterations of the algorithm. 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. 

A Deep Reinforcement Learning Framework for Column Generation
Cheng Chi University of Toronto
Amine Mohamed A bbuussala New York University
Elias Khalil University of Toronto
Juyoung Wang University Toronto
Zoha Sherkat-Masouee
University of Toronto
Abstract
Column Generation (CG) is iterative algorithm for solving linear programs (LPs) with an extremely large number of variables (columns). CG is the workhorse for tackling large-scale integer linear programs, which rely 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 route, of which there are exponentially many; CG incremen- tally grows the subset of columns being used, ultimately converging 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 each iteration, problem: the column selected in a given iteration affects subsequent column selec- tions. This perspective lends itself to Deep Reinforcement Learning approach that uses Graph Neural Networks (GNNs) to represent the the I.P interest. 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 commonly used greedy policy. Our code is available at this link.
optimal
treat CG sequential decision-making
constraint structure
1 Introduction
Machine Learning (ML. Mathematical Optimization (MO) a growing field with wide range of recent studies that enhance optimization algorithms by embedding ML in them to replace human- designed heuristics [Bengio et al., 2021]. Previous work has overwhelmingly focused on combina- torial or integer programming problems/algorihmms for which all decision variables are explicitly given in advance. For example, in a knapsack problem, each binary variable represents the decision include or exclude an item integer programming solvers heuristics assign values to without any memory issues. However, there are many optimization problems which there are more decision variables than one could ever explicitly deal with. In VRPTW, for example, each binary variable represents the decision to include or exclude route, of which there are exponentially many.
knapsack; even with hundreds of thousands of items, modern
all variables simultancously
Column generation (CG) is algorithm for solving linear programs (LPs) with prohibitively large number of variables (columns) [Desaulniers et al., 2006). It leverages the insight that in an optimal
"Corresponding author: khali 10mie utoronto.co.
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

solution to LP, only a few variables will be active. In each iteration of CG, a column with negative reduced cost added a Restricted Master Problem (RMP, where "restricted" refers the use of only a subset of columns) until no more columns with negative reduced cost are found. When that occurs, CG will have provably converged to an optimal solution to the L.. To solve an integer linear program, CG can be used an LP relaxation solver within the so-called branch and price algorithm. In this work, we will focus on CG as an algorithm for solving large-scale linear programs; our conclusion section discusses the straightforward application of our method to the integer case.
A commonly used heuristic rule is to greedily select the column with the most negative reduced cost in each iteration. However, is this always the "optimal" column to add if one is interested in converging in as few iterations as possible? Could ML-guided column selection, based on the structure of the current instance being solved, make better selection decisions that speed up the convergence of CG? These are the questions we tackle in this work. We adopt the standard view that one is interested in solving problem instances that have the same mathematical formulation but whose data (objective function coefficients, constraint coefficients, num. of vehicles, etc.) differ and are drawn from the same distribution. In VRPTW, for example, the geographical locations of customers that must be served by the vehicles may vary, as do the corresponding service time windows.
To tackle these questions, we propose a MI. framework to accelerate the convergence of the CG algorithm. In particular, we utilize RL to select columns for LPs with many variables, where the state of the CG algorithm and the structure of the LP instance are encoded using GNNs that operate on a bipartite graph representation of the variable-constraint interactions, similar to Gasse et al. [2019]. Q-learning is used to derive column selection policy that minimizes the total number of iterations through an appropriately designed reward function. Our premise is that by directly optimizing for convergence speed using RL on similar LP instances from the same problem (e.g.. CSP, VRPTW), one can outperform traditional heuristics such as the greedy rule. Our contributions can be summarized as follows:
1. CG as a sequential task: We bring forth the first integration of RL. and CG which appropri- ately captures the sequential decision-making nature of CG algorithm. Our RI. agent, RLCG, learns Q-function which takes the future rewards (namely, total number of iterations) into consideration and therefore can make better column selections each step. In contrast with prior work on RL for mathematical optimization, ours is, to our knowledge, the first to tackle the very widely applicable class of problems with exponentially many variables.
2. Curricula for learning over diverse set of instances: In practice, instances of the same optimization problem may vary not only in their data, but also their sizc/complexity. For example, in the CSP, instances may vary in the number of rolls that must be cut. To enable efficient RL over a widely varying instance distribution, we show how curriculum can be designed for given dataset of instances with a minimal amount of domain knowledge.
3. Evidence of substantial improvements over existing myopic heuristics: We evalu- ate RLCG on the CSP, which is known as the representative problem in this domain [Ben Amor and Valerio de Carvalho, 2004, Desaulniers et al., 2006), and the VRPTW, another widely studied and applied problem. We compare RLCG with the commonly used greedy column selection strategy and an expensive, integer programming based one-step lookahead strategy described by Morabit et al. [2021]. Our algorithm converges faster than both of these in terms of the number of iterations and total time. Our results show the value of considering CG as a sequential decision-makinng problem and optimizing the entire solving trajectory through RI..
2
Related Work
Work the use of RL to guide iterative algorithms can be traced back to Zhang and Dietterich [1995], who used RL for a scheduling problem. More recently, Dai et al. [2017] and Bello et al. [2016] proposed deep RL for constructing solutions to graph optimization problems: the survey by Mazyavkina et al. [2021] summarizes subsequent advances in this space. Dai et al. [2017] were the first to use GNNs in this setting, a line of work that has also grown substantially (c.g.. Cappart al. [2021]) including in integer programming [Gasse al., 2019]. Relatedly, Tang al. [2020]

---

apply RL to the cutting plane algorithm for integer linear programming, where a policy that selects "good" Gomory cuts is derived using evolutionary strategies. Within the framework of Constraint Programming, Cappart et al. [2020] present a deep RL approach for branching variable selection within an exact algorithm. Nonetheless, to our knowledge, the sequential decision-making perspective has not been leveraged in the context of column generation or integer/linear programming with many variables, a setting which is relevant to many practical applications such as resource allocation (e.g.. CSP), routing problems (c.g., VRPTW), and airline crew scheduling [Barnhart al., 2003].
The closest work to ours is that of Morabit et al. [2021]. They formulate the column selection in each CG iteration column classification task where the label of each column (select not) is given by an "expert". This "expert" performs a one-step lookahead to identify the column which maximally improves the LP value of the Restricted Master Problem (RMP) of the next iteration. This done with an extremely time-consuming mixed-integer linear program (MILP)). The RMPs are encoded using bipartite graphs with columns nodes (v) and constraint nodes (c), where an edge between v and in the graph indicates the contribution of a column is then annotated with additional useful information for column selection stored as node features. Morabit al. [2021] then use GNN to imitate the node selection of the expert using supervision, similarly to what was done for branching by Gasse et al. [2019].
a constraint Each node of the graph
contrast, our work treats the column generation utilizes RL to select a column at each iteration of CG. Our GNN acts as Q-function approximator that maximizes the total future expected reward. As such, our work focuses on directly reducing the total number of CG iterations, whereas Morabit et al. [2021] derive classifier that does not consider the interdependencies across iterations, treating them as independent. One approach to accelerate CG further is add multiple columns per CG iteration Desaulniers et [1999]; we discuss this extension in the Conclusion.
sequential decision decision-making problem and
3 Preliminaries: Column Generation
We will use the canonical Cutting Stock Problem (CSP) describe the CG method is typically done in textbooks on the topic [Desaulniers et al., 2006]. CSP is general resource allocation problem where the objective is to subdivide a given quantity of a resource into number of predetermined allocations to meet certain demands so that the total usage of the resources (e.g., total number of size- fixed paper rolls) minimized. Such minimization is achieved by finding a set of optimal divisions of each resource, in other words, using set of optimal cutting patterns to divide resources. Due to the CSP's s combinatorial nature and its exponentially large set of possible patterns (variables). CG is used solve the LP relaxation of CSP iteratively without explicitly enumerating all possible patterns.
The CSP formulation and column generation algorithm we use is a common modification Gilmore and Gomory [1961]. The set of all feasible patterns P that can be cut from a roll is defined as:
P
F& E N" Σ a.aa S L, z.
Vi f1,,,,...,,,,,, Vk Vk E {1, (1,2,.... .PII....II]]]
where each pattern P is represented using vector 2; E N". With a, being possible cut length from a roll with length I., each element of Ty specifies how many such cuts with length a are included in pattern p. For instance, assume the length of the resource roll L is 4m, so all possible a,s are 1m, 2m, 3m and 4m, and then one possible cutting pattern is represented by Let Ap the number of times pattern p is used. The formulation with Ao being a decision variable
(0, 2, 0. 0).
min ACNIPI
TipAp d, Vi (1.2.
PEP
PEP
where the objective function minimizes the total number of patterns used, which is equivalent to minimizing the number of rolls used, The constraints ensure demand is met, while enforcing the integrality restriction on Ap-
This problem has extremely large number of decision variables as P is exponentially large. Therefore, the problem is decomposed into the Restricted Master Problem (RMP) and the Sub- Problem (SP). The RMP is obtained by relaxing the integrality restrictions on Xp with an initial set P
3

---

where P C. The RMP formulation of the cutting stock problem is defined as follows:
min AENIIP P1
Σxp
Σ 1p
Σ
Tip d4 Vi (I,... m) 20
PEP
PEP
The SP formulation of the provided cutting stock problem defined as follows:
Σ O S
mim
JEN
where n, the dual value associated with demand constraints. The SP is used to generate a pattern p represented by vector E N with the most negative reduced cost, then adding that to P in the next iteration. Below, we provide an overview of the column generation algorithm, noting that our method will intervene Step make potentially non-greedy column selection decision:
1. Solve the RMP to obtain X and म;
2. Update the SP objective function using
3. Solve SP to obtain a
1 E Ka4y I 0, add the column associated with x; and return to step 1, else Stop.
4 The RLCG Framework
RMP
RL suggested column
RMP
Bipartite
graph of current CG
Dual values
RL
New column
Dual values
Candiclate columns
SP
SP
CG
RLCG
Figure 1: High-level comparison standard Column Generation (CG) and RLCG.
At high level, our RL-aided column selection strategy, RLCG, works as follows. We assume that the sub-problem (SP) solved at each iteration and a set near-optimal column candidates returned, which is general feature of optimization solvers such Gurobi. While the greedy CG algorithm, as described in Section 3, adds the single column with the most negative reduced cost from G to the RMP of the next iteration, RLCG selects columns from & according to the Q-function learned by the RL agent. The RL agent is fused within the CG loop and actively selects the column be added to the next iteration using the information extracted from the current RMP and SP. An illustration comparing CG and RLCG provided in Figure 1.
4.1 Formulating CG as MDP
We formulate CG as a Markov decision process (MDP). As is customary, we use (8, A. T.r. 7) to denote our MDP, where S is the state space, A the action space, T S x S x A + [0.1] (s', s, a) + P(s'|s, ls, a) the transition function, r: A A + R the reward function, and 7 E (0,1) the discount factor. We train the RL agent with experience replay [Mnih al., 2015].

---

4.1.1 State space S
The state represents the information that the agent has about the environment, In RLCG, the environ- ment is the CG solution process corresponding to a given problem instance. As shown Figure 1, the information passed the RL agent is the bipartite graph of the current CG iteration from the RMP and the candidate columns from the SP. At each iteration, the RMP is an LP as shown in Section 3. As introduced in Gasse al. [2019], such an LP is encoded using bipartite graph with two node types: column nodes V and constraint nodes C. An edge (u, c) exists between node v E y and a node с E C if column contributes to constraint c. An example bipartite graph representation of the state is shown in left of Figure 2 with column nodes shown on the left hand side, the constraint nodes on the right hand side, and the action nodes, which are the candidate columns returned from the SP, are shown in green (e.g.. v6, u7).
To incorporate richer information about the current CG iteration, we include node features for both column nodes and constraint nodes (vf and ef next the nodes). We designed 9 column node features and 2 constraint node features in our environment based on our previous experience with CG and inspiration from Morabit et al. |2021]. These node features are descrihed Appendix G.
As such, the state space S is the space of bipartite graphs representing all possible RMPs from the problem instances drawn from the distribution with the node features given above. The bipartite graph shown in the left of Figure 2 is particular state in S. As states are bipartite graphs with node features, it is natural to use a Graph Neural Network (GNN) as the Q-function approximator in our DQN agent. This bipartite graph representation not only encodes variable and constraint information in the RMP, but also interactions between variables and constraints through its edges.
4.1.2 Actions, transition, and reward
Action space A. As shown in Figure 2, the RL agent selects one column to add the RMP for the next iteration from the candidate set G returned from current iteration SP. Therefore, the action space A contains all possible candidate columns that can be generated from SPs; for example, the green nodes u6 and v7 in Figure 2. As the action space is discrete and the state space is continuous, the GNN (Q-network) performs the operation of returning action values in the current state, i.e., á(s, a1; w), ..., ((3, ami w).
Transition function T. Transitions are deterministic. After selecting an action from the current candidate set G, the selected column enters the basis in the next RMP iteration. We then delete the action nodes that were not selected from the bipartite graph (current state), turn the selected action node into column node, solve the new CG's RMP and SP, update all the features, and augment all the action nodes returned from the next SP iteration into the left-hand side of the graph, which results in a new bipartite graph state. Take the bipartite graph state shown the left of Figure 2 as an example, and assume action v6 is selected at this iteration. The transition occurs as follows: v6 (in grey) becomes a column node, and candidate columns v8 and v9 returned by SP (in green) are added.
41
42
41
di
Select action
d2
16
114
V7
Figure 2: State transition: Two green action nodes are considered, one of them is selected, transition- ing to a new state.

---

Reward function R. The reward function consists of two components: (1) the change the RMP objective value, where bigger decrease in value preferre:: unit penalty for each additional iteration. Together, they incentivize the RL agent to converge faster. The reward at time step t is defined as:
objj - obje objo
Pt = a
1,
(1)
where objo the objective value of the RMP in the first CG iteration and is used normalize (obj.-1 obj,) across instances of various sizes; is non-negative hyperparameter that weighs the normalized objective value change the reward.
4.2 RLCG training and execution
Algorithm shows how a trained RLCG agent is applied to solve problem instance. The MDP components A. r)) used in this section are defined in Section 4.1. Before starting the iterative optimization, the initialization steps 1-3 build the initial bipartite graph with computed node features and add an initial set of columns into basis (for instance, in CSP, we first add simple cutting patterns into the basis to initialize). Inside the while loop, a column selected from the candidate set based on the best Qavauu computed by the RL agent. Then, the RMP and the SP updated in the same way as the traditional CG algorithm. The MDP model corresponds to extracting the MDP components from the current updated RMP and SP, which are discussed in Section 4.1.1 and Section 4.1.2. Steps 7, 8 correspond to the deterministic state transition T described in Section 4.1.2, and S is the resulting state due to action aj.
Algorithm 1: RLCG (RL-aided column generation algorithm)
Input: Problem instance p from distribution D & trained Q-function. Output: Optimal solution
f == Og RMPo Initialize(p)
Solve RMP, get dual values; Use dual values to construct SPo.
3 (So, Ao, To: Ro} = MDP(RMP,,.SP)
4 while CG algorithum has not converged do
at arg maxo, EA, Q(S:, Va, A
Add variable ot to RMP, and get RMP++1
7 Solve RMP,+1 to get dual values: Use dual values to build SP
(S.41.A44. Te41, Re+1) MDPRRMP, SP...))
t=t+1
end
Return optimal solutions from RMP, SP.
Training. The DQN algorithm with experience replay is used [Mnih et al., 2015] with the typical mean squared loss between Q(0,, a) and Qurzer (S0, a) V (all green action nodes) in bipartite graph state So- Quarea(So, a) is defined as 1---y-ma,,, Q($1, a). A GNN is used as Q-function approximator. Training instances are sequenced based on a domain-specific curriculum described for each of CSP and VRPTW in Section 5.
5 Experimental Results
Baseline strategies and evaluation metrics. To assess the performance of RLCG, we consider two baseline methods: the greedy column selection strategy (most negative reduced cost) and the MILP expert column selection of Morabit et al. [2021] as described in Section 2. This expert provides an upper bound on the performance of the supervised learning approach of Morabit el al. [2021], ]], as their ML model approximately imitating the expert, i.e., will never select better columns than the expert. We consider two standard evaluation metrics: (1) Number of iterations for CG to converge; (2) Time seconds. For the latter, this includes GNN inference time and feature computations for RLCG. Our computing environment described in Appendix Section C.

---

5.1 Cutting Stock Problem (CSP)
Dataset. We use BPPLIB Delorme et [2018], widely used collection of benchmark instances for binary packing and cutting stock problems, which includes number of instances proven to be difficult to solve [Delorme and lori, 2020, Wei et al., 2020, Martinovic et al., 2020]. BPPLIB contains instances of different sizes with the roll length varying from 50 to 1000 and the number of orders m varying from 20 to 500. Our training set has instances with n 50, 100, 200. The remaining instances with 50, 100, 200, 750 are split into a validation set and testing set, with hard instances n = 750 only appearing in the testing set, as it is very expensive to solve such large instances during training. The detailed statistics of these three sets are listed in Table 4 in Appendix E. Note that test set is more challenging than that used in training, allowing to assess the agent's generalization ability.
Curriculum Design. In the RL context, curriculum learning Narvekar et al. [2020] serves sort the instances that RL agent observes during the training process from easy to hard. In our experiments, we noticed that adopting the curriculum learning paradigm improves the learning of the RL agent and results in better column selection and faster convergence. We train our RLCG agent by feeding the instances in order of increasing difficulty. For CSP, instances are sorted based on their roll length n and number of orders to build training curriculum (Table 5 in Appendix C). The detailed comparison of training with and without the curriculum is deferred to Appendix A. In short, the former crucial to convergence when the training set contains instances of varying difficulties. The overall training process
Hyperparameter tuning. We briefly describe the outcome of large hyperparameter tuning effort which is described at length in Appendix B. We tune the main hyperparameters, in the reward function (1), the exploration probability in DQN, the discount factor, and the learning rate Ir in gradient descent. A grid with 81 possible configurations is explored by sampling 31 configurations, training the agent, and evaluating them on a validation set. The majority of the configurations resulted in agents that outperform the greedy strategy (see Appendix B Figure 10). The best configuration is: a = 300, 0.05, = 0.9 and Ir = 0.001. For all the experiments conducted below, we use this configuration, both for CSP and VRPTW.
0000 0100 m0d
Sedocs --0 14
(a) CG iterations, 50
(b) CG iterations, 200
(c) CG iterations, 750
3:00
Toa 570
50 20
300
www.
(d) Time seconds,
(e) Time in seconds, n 200
(l) Time in seconds, 71 750
Figure 3: CSP: Scatter plots of CG iterations (top row) and running time (bottom row) with RLCG the horizontal axis and Greedy (Expert) on the vertical axis, respectively, each three pairs of sub-figures. Each point represents test instance of given size Points above the diagonal indicate that RLCG is faster than the competitor.
Performance comparison. Figure 3 shows pair-wise comparisons between RLCG and the two baselines in terms of the number of CG iterations (top row) and solving time (bottom row) on the testing instances. Each point in a plot corresponds
test instance. Across all and for both baselines in Figure 3, the majority of the points are above the diagonal line, which indicates that RLCG outperforms the competing method w.r.t. the evaluation metric. Such a tendency becomes more pronounced as the CSP instances become larger (left to right). RLCG performs better than the greedy

---

column selection for all the roll lengths n and the performance improvement becomes larger as n grows. For CSP instances with 50 and n 200, the MILP expert is able to maintain similar performance compared to RL. However, solving the MILP expert requires solving MILP each iteration with only one-step lookahead which is time consuming. For CSP instances with 750, RLCG begins outperform the MILP expert due to its ability to take future rewards into consideration.
200
textor
:30
(a) CG iterations,
50
(b) CG iterations, 200
(c) CG iterations,
750
1000
43
000
600
400
(d) Time seconds, 50
(e) Time in seconds, 200
Time in seconds, 750
Figure 4: CSP: Box-plots of CG iterations (top row) and running time (bottom row) for the proposed method, RL (green), Greedy (red), and Expert (blue). Each box represents the distribution of the iterations or running time for a given method and roll size Lower is better.
Notice that though did not train RLCG using CSP instances with 750, able perform well on such instances, indicating strong generalization to harder problems. We also generate box plots to compare statistically the three methods shown Figure 4. Detailed statistics can be found in Table 6, As shown by all the subplots in Figure 4, especially for large instances in the subplots (c) and (f), the proposed RLCG achieves statistically meaningful improvements on the CG convergence speed compared to both the greedy and the expert column selection methods.
Comergencce picts for rest notannes of site -
Conoargence pizta instercaes size
Convergence plots teat Inclances of $2e 700
Gremb
Bieed
Cramb
0.
2.
08
(a) CSP, 50 test instances
(b) CSP
200 test instances
(c) CSP, 750 test instances
Figure 5: CG convergence plots for CSP. The solid curves are the mean the objective values for all instances and the shaded shows +1 standard deviation.
Convergence plots. In Figure 5, we visualize the CG solving trajectories for all test instances for n 50, 200, 750. We record the objective values the RMP each CG iteration for given method, then take the average over all instances. Note that we normalized the objective values to be in [0. I before taking the average among instances. Since the MILP expert is by far the slowest, we restricted attention the two less expensive methods: RLCC and Greedy. Looking at Figure 7, it is clear

---

that not only does RLCG terminate in fewer iterations and less time, but also dominates Greedy throughout the CG iterations. In other words, if one had terminate CG earlier, RLCG would result in a better (smaller) objective value as compared to what Greedy would achieve.
5.2 Vehicle Routing Problem with Time Windows (VRPTW)
The VRPTW seeks of possible routes for given number of vehicles to deliver goods group of geographically dispersed customers while minimizing the total travel costs. In the language of CG, each route is one column and there are exponentially many. Constraints of VRPTW include: vehicle capacity; a vehicle has to start from depot and return to it; all customers should be served exactly once during their specified time windows. The detailed formulation of VRPTW is given by Cordeau al. [2002]]; implementation details are in the appendix.
Dataset. We use the well-known Solomon benchmark [Solomon, 1987]. This dataset contains six different problem types (C1, C2, RI, R2, RC1, RC2), each of which has 8-12 instances with 50 customers. "C" refers to customers which are geographically clustered, "R" to randomly placed customers, "RC"
mixture. The "1" and "2" labels refer to narrow time windows/small vehicle capacity and large time windows/large vehicle capacity, respectively. The difficulty levels of these sets are in order of C, R, RC. There are 56 instances in total in Solomon's 's dataset, and from each original Solomon instance, we can generate smaller instances by considering only the first 50 customers.
We use instances from types CI, RI, RCI for training. For the training we generated 80 smaller instances per type from the original Solomon's 's instances by only considering the first n customers where randomly sampled from 5-8, for total of 240 training instances. For testing, of instances are considered: (1) 60 small-size instances (number of customers n within same range as training instances); (2) large-size instances (number of customers from 15-30). All the test instances either generated from held-out Solomon instances (c.g., sets C2, R2, RC2) generated from some training instance but with a much different n.
sets
Curriculum Design. As in CSP, we designed curriculum for VRPTW that sequences instances in order of difficulty: C1, R1, then RC1. This order is based on the fact that clustered instances have structure that enables "compact" routes for neighboring customers, whereas random instances require more complex routes. The mixed RCI instances require reasoning about both types of customers simultancously [Desrochers, 1992].
Time CONEET
15000
Teee 1200
Tandion FILG
FLLO
Time FILO
(a) VRPTW with small instances
(b) VRPTW with large instances
Figure 6: VRPTW: Scatter plots of CG iterations and running time with RLCG. Each point represents a test instance of given size n. Points above the diagonal indicate that RLCG is faster than greedy.
Performance comparison. The hyperparemeters of the RL agent are chosen to be the same as the best set of hyperparameters found for CSP. Figure 6 shows similar trends those seen for CSP: RLCG converges in fewer iterations and less time than Greedy most instances.
This effect more pronounced for the large VRPTW instances. fact that can also be observed in the convergence plot of Figure (b): RLCG converges in roughly 100 iterations compared to 300 iterations for Greedy, on average. Additional box plots are deferred to Appendix J. Note that we do not compare the Expert here given that it is much too slow and practically intractable.

---

Convergence email lest instances
Convergence plots large instances
Greedy
Groedy
1.0
1.0
Relative objecive value
0.8
0.8
abjestve
0.6
0.4
0.4
0.2
0.0
100
200
Column Generation
Generation Iteration
(a) VRPTW, Small test instances
(b) VRPTW, Large test instances
Figure 7: CG convergence plots for VRPTW. The solid curves are the mean of the objective values for all instances and the shaded area shows +11 standard deviation.
6 Conclusions & Discussion of Limitations
RLCG shows superior performance and better convergence both in terms the number of iterations and time compared the greedy column selection and the MILP expert strategy. In addition, curriculum learning enables the agent to generalize well when facing harder test instances. Our experiments on two important large-scale I.P families show that there value in modeling CG as a sequential decision-makinn problem: taking the future impact of adding column into account helps convergence.
However, current work is restricted to adding only one column per CG iteration. Adding multiple columns per iteration can speed up convergence. However, this makes the RL action space exponential and thus finding the action with the largest Q-value becomes combinatorial optimization problem. Recent work by Delarue et al. [2020] addresses this problem, and thus our RL formulation can be expanded using the results of this paper to allow for multiple columns. Alternatively, policy gradient methods could be used instead of Q-learning. We believe this is an exciting next step but one that stretches beyond the limits of our paper, which the first ever on RL for CG. A trained RLCG agent also be embedded within the branch and price algorithm for solving the integer-constrained versions of CSP/VRPTW and invoked to solve each LP relaxation. The speed-ups demonstrated herein would transfer to that setting, assuming that an appropriate dataset of training and validation instances can be collected.
Acknowledgments: Khalil acknowledges support from the Scale AI Research Chair Program and an NSERC Discovery Grant.

---

References
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405-44) 2021.
Guy Desaulniers, Jacques Desrosiers, and Solomon M. Marius. Column generation a primer in column generation. Springer, page 1-32, 2006.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Hatem Ben Amor and Jose Valerio de Carvalho. Cutting stock problems in column generation. Springer, page 1-32, 2004.
Mouad Morabit, Guy Desaulniers, and Andrea Lodi. Machine-learning -aasadd based column selection for column generation. Transportation Science, 55(4):815-831, 2021.
Wei Zhang and Thomas G Dietterich. A reinforcement learning approach to job-shop scheduling. In IJCAI, volume 95, pages 1 1114-1120 120. Citeseer, 1995.
Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Irwan Bello, Hieu Pham. Quoc V Le. Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint 1oX1::6111.099400) 2016.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for
combinatorial optimization: survey. Computers & Operations Research, 134:105400, 2021.
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint arXiv:2102.09544, 2021.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning to cut. International Conference on Machine Learning, pages 9367-9376. PMLR, 2020.
Quentin Cappart, Thierry Moisan, Louis-Martin Rousscau, Isabeau Prémont-Schhee and Andre Cire. Combining reinforcement learning and constraint programming for combinatorial optimization. arXiv preprint arXiv:2006. 01610, 2020.
Cynthia Barnhart, Amy M Cohn, Ellis L Johnson, Diego Klabjan, George L Nemhauser, and Pamela Vance. Airline crew scheduling. In Handbook of transportation science, pages 517-560. Springer, 2003.
Guy Desaulniers, Jacques Desrosiers, and Marius Solomon. Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems. 15, 01 1999, doi: 10.1007/ 978- 1--1-11----17---4 14.
P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting-stock problem. Operations research, 94)) 1961. ISSN 0030-364X. doi: 10. 10.1287/pre.9.6688 URL bttps://doi.. wrgg/oo//// 10. /p2///pre... .9. 849.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-5333 2015.
Maxence Delorme, Manuel Iori, and Silvano Martello. Bpplib: a library for bin packing and cutting stock problems. Optimization Letters, 12(2):25--250 2018.

---

Maxence Delorme and Manuel lori. Enhanced pseudo-polynonen formulations for bin packing and cutting stock problems. INFORMS Journal on Computing, 32(1):101-119, 2020.
Lijun Wei, Zhixing Luo, Roberto Baldacci, and Andrew Lim. new branch-and setth-annd--r--e--ae pri-c--nnddeuut algorithm for one-dimensional bin-packing problems. INFORMS Journal on Computing, 32(2); 428-443, 2020.
John Martinovic, Maxence Delorme, Manuel lori, Guntram Scheithauer, and Nico Strasdat. Improved flow-based formulations for the skiving stock problem. Computers Operations Research, 113: 104770, 2020.
Sanmit Narvekar, Bei Peng. Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: A framework and survey, arXiv preprint S0tV::20030046600 2020.
J.-F. Cordeau, G. Desaulniers, J. Desrosiers, and F. Soumis. The vrp with time windows. SIAM Monographs Discrete Mathematics and its Applications, pages 157-193, 2002.
M. Solomon. Algorithms for the vehicle routing and scheduling problem with time window constraints. Journal of Service Science and Management, 35:254-265, 1987. URL https: //wp:://www.../ sintef.
Jacques Desrosiers; Marius Solomon; Martin Desrochers. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2):34--354, 1992.
Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with combi-
natorial actions: An application to vehicle routing, Advances in Neural Information Processing Systems, 33:609-620, 2020.
12


Reviews:
[{"review_id": "yXv8NXmUZIa", "reviewer": "Reviewer_DMVD", "summary": "The paper proposes a reinforcement-learning-based approach for column selection within a column generation procedure to solve an LP relaxation. Candidate columns come from a set of solutions encountered while solving the column generation subproblem, and Q-learning is applied to choose a column, rewarding large changes in objective value and few iterations. Computational results on cutting stock and vehicle routing problems show that this approach reduces number of iterations and solve times by a significant margin compared to standard column generation (at the cost of training on instances from the same family).", "questions": "Minor suggestions related to clarity and details:\n\n* Please specify in Appendix C which PoolSearchMode parameter you are using in Gurobi to find the 10 candidate columns. It is useful to know if these are the top 10 candidates, or 10 incidental candidates during search.\n\n* In Appendix C, it refers to the code for the network structure. Could you please describe the network structure in the appendix?\n\n* Notes on text: Missing figure reference in line 176. Typo \"hyperparemeters\" in line 304. Some of the citations need to be with parenthesis.\n\nI have a few questions that are not necessary for this submission, but mostly for my own curiosity:\n\n1. Have you considered keeping some of the older column candidates, perhaps with some system to age them out of the graph as needed? This could be helpful in two ways: a previous good column is still there if the RL agent ends up choosing a bad column by mistake, or if there is more than one column worth selecting in an iteration.\n\n2. Have you considered adding more than one column per iteration (i.e. between subproblem solves)? This would be an easy way to consider multiple columns. It might work better if you keep older candidates as described above.\n\n3. Do you know what features were important to select good columns? If this is insightful (e.g. if a particular feature that is not reduced cost stands out, or if it is still mainly reduced cost), I believe this would be a nice contribution to include in the paper. It would be great to know if one can extract heuristic insights that can be incorporated back into standard column generation, without lengthy training times. In addition, I am curious how much the problem-specific features matter, since ideally it would be good to have this work out-of-the-box without problem-specific features.", "limitations": "No further limitations other than the ones discussed above. The paper does a decent job at discussing its limitations at the end.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is a solid step in improving the scalability of problems in Operations Research using machine learning techniques. Column generation is an important technique to solve large-scale problems with exponentially-many columns, and the paper provides concrete evidence that a reinforcement-learning-based approach can be successful at selecting good columns, assuming one has a set of instances that can be trained on. While the RL formulation and neural network architecture mostly follow the literature standard, it is sound and novel (as far as I know). Furthermore, it is useful to know that curriculum learning helps in this approach. The computational experiments are well-designed and reasonably extensive: it includes hyperparameter tuning and a good number of practical instances. The improvements from this method are substantial in the context of machine learning techniques for OR, particularly for larger instances.\n\nI do not have any major concerns with the paper. The paper might have been slightly stronger if it compared with column generation with stabilization, but the method is already taking fewer iterations than a look-ahead expert, and thus this comparison might not be necessary.\n\nOverall, everything looks solid in the paper and I believe this is a valuable contribution. I recommend this paper to be accepted.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nO_fR2uIYV", "reviewer": "Reviewer_Sm39", "summary": "This paper studies the use of reinforcement learning to improve the column generation algorithm. In particular, the authors design a state space around a bipartite graph containing column nodes and constraint nodes, and an action space derived from RMP and SP formulations of the problem. These two aspects are the main challenge of the translation, the reward function is then set to a reasonable choice, and a standard RL algorithm (DQN) is applied. Testing in two problems (cutting stock and vehicle routing) show their method outperforms a baseline. ", "questions": "Questions:\n* Sec. 3: I have trouble understanding how the SP formulation follows from the RMP formulation (Line 130). The transition here is very abrupt, where does \\pi come from, how is it computed from the RMP, etc. A figure (conceptual example) would help here a lot as well.   \n* L165-168: You design column node features and constraint node features based “based on our previous experience”. Are these features problem independent? How vital are they for your method? Can you really defer this to the appendix? \n* L 172: It is unclear from the text how the exact GNN looks like. I do understand the bipartite graph structure, but how are all combined node embeddings mapped to the Q-function output? You need to at least briefly mention something about this in the main paper text. \n\n\n\nConclusion: This is a decent paper. The main contribution of the paper is the adaptation of CG to the RL setting. The main challenge is the way to represent the state space (as a bipartite graph), and the use of RMP and SP formulations to design an action space at each iteration. They can then apply any standard RL method, like DQN in this paper. The method subsequently outperforms the baseline. There have been many new applications of RL to combinatorial optimization problems in recent years (which makes the paper less groundbreaking), but it does seem to be a valuable addition. ", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong:\n* The application of RL to combinatorial optimization is a relevant research topic that gets more and more attention.\n* The method outperforms the baseline on two relevant problems (cutting stock problem and vehicle routing problem with time windows).  \n* I like Figure 1, it clarifies a lot. \n* You open source your code. \n\nWeak:\n* See questions section. \n* There are very little details on the RL side of things (like a DQN update equation or target computation). I understand your focus is on the adaptation of column generation to RL, but I do think one or two paragraph with an equation would help a lot. \n* You repeatedly point to Figure 6 in Appendix A, but if that is important to explain your method, it should appear in the main paper. \nIn general you have quite a lot of text and little conceptual illustration. I think a good Figure 1 showing your method could help a lot.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JRsKnXmFqF", "reviewer": "Reviewer_8Csh", "summary": "This work focuses on using Column Generation (CG) as an algorithm to solve large-scale linear programs. A DQN algorithm (called RLCG) combined with Graph Neural Networks is used to improve the column generation procedure. Specifically, RL is used to select columns for linear programs with many variables. To do so, it assumes that the Sub-Problem (SP) is solved at each iteration and a near-optimal set of column candidates G is returned. The greedy approach selects columns with the most negative reduced cost whereas the RL approach selects columns from G according to the Q-function learned by RLCG. RLCG converges faster and generates fewer iterations for the Cutting Stock Problem (CSP) and the Vehicle Routing Problem with Time Windows (VRPTW), compared to a greedy policy. In some cases it has similar performance to MILPs, although as the problem size increases, appears to outperform them as well.  ", "questions": "Column Generation is only introduced on the 3rd page. The authors need to restructure this as many readers will probably not be familiar with CG and will therefore not understand much in the first 2 pages.\n\nYou mention that RLCG is unable to train on instances of n=750 as it is expensive to solve such instances during training. Is scalability a fundamental limitation of the approach?\n\nHow sensitive is the curriculum training process? Is it easy to build a curriculum? What happens if you do not use a curriculum?\n\nFor the Vehicle Routing problem, how does RL compare to MILPs?\n\nLine 39: The authors don’t seem to tackle the integer case which is what they claimed CG is mainly used for. As such, I’d like the authors to help me better understand the significance of these results.\n", "limitations": "The authors mention some limitations, such as adding a single column per CG iteration. However, there are a couple of other limitations that I think should be noted:\n\n1.Scalability - it seems that, as the problem size increases, it becomes increasingly expensive to train the agent, to the point where it is not feasible. I do not have good intuition as to whether n=750 is difficult in the CSP problem for example, so it would be good for the authors to discuss the scalability challenges and significance of their results in more depth.\n\n2. Performance compared to MILP - the authors need to be more specific as to how their method compares to MILP as they are both competitive. A statistical analysis would be important here to better understand where each method has its strengths and weaknesses. Replacing Figure 3 with this analysis would be helpful, as I dont get much insight from these figures.\n\n3. When introducing the CG problem, the authors mention that it is the workhorse for tackling large scale integer linear programs. However, the authors then state that they do not tackle the integer case (line 39). This paper would be greatly strengthened, in my opinion, if the authors explain the significance of their results and/or provide an example tackling the integer case. A strong argument here will influence my score.\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: \nThis paper appears to be original as I am unaware of RL being used for Column Generation. Utilizing graphnets to encode the state of the CG algorithm as well as the structure of the LP instance also appears to be a novel contribution.\n\nQuality: \nThe paper is well written and the authors appear to do a good experimental comparison with the baseline algorithms. In addition, experimental results are shown on multiple domains which further strengthens the results.\n\nClarity: \nColumn Generation is only introduced on the 3rd page. The authors need to restructure this as many readers will probably not be familiar with CG and will therefore not understand much in the first 2 pages.\n\nFigure 2: The axes are very hard to read\n\nSignificance: \nIt is difficult for me to judge the significance of the results. When introducing the CG problem, the authors mention that it is the workhorse for tackling large scale integer linear programs. However, the authors then state that they do not tackle the integer case (line 39). This paper would be greatly strengthened, in my opinion, if the authors explain the significance of their results or alternatively, provide an example tackling the integer case. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6QDD_6_6wT0", "reviewer": "Reviewer_Eksw", "summary": "This work considers the problem of using machine learning (ML) to speed up the time to solve linear programmes (LPs) with a large number of columns (variables). Approaches to solving such problems fall under the category of column generation (CG); an approach whereby columns (variables) in the LP are iteratively selected from among the candidates to add to the restricted master problem (RMP) until no more columns with a negative reduced cost in the RMP are available, at which point a provably optimal solution to the LP will have been found. Classical approaches to CG typically follow a greedy policy whereby the column which leads to the most negative reduced cost is selected at each iteration. The authors posit that such a myopic approach does not necessarily lead to the fewest overall iterations to find the optimal solution to the LP. Instead, the authors propose a reinforcement learning for column generation (RLCG) method which treats column generation (CG) as a Markov decision process (MDP). Using this formulation, the authors train a policy parameterised by a graph neural network (GNN) with deep Q-learning (DQN) to, at each CG iteration, select the column which maximises the long-term return (which, in their setting, corresponds to minimising the overall number of CG iterations). The authors test their approach on the canonical cutting stock problem (CSP) and vehicle routing problem with time windows (VRPTW). They demonstrate that their method can outperform both a greedy heuristic and a 1-step-lookahead expert in terms of both solving time and decision quality (as measured by the overall number of CG iterations).", "questions": "* **Missing related work and context:** The authors discuss the work of Morabit et al. 2021, which they claim is the only prior work to have applied ML to CG. However, a quick search revealed there are at least a couple of other ML-for-CO approaches which have been proposed (e.g. Shen et al. 2021 and Babaki et al. 2022). The related work section should be more comprehensive to put the authors’ work in the context of the current literature.\n\n* **Missing experimental baseline comparisons:** \n\n    * Despite the availability of the above ML-for-CG algorithms, and despite the authors referring to the work of Morabit et al. 2021, the authors provide no comparison to any ML-for-CG baseline in the experiments section. Instead, the authors only compare to a simple greedy heuristic and to the 1-step-lookahead expert used by Morabit et al. 2021 for the data labeling process. The authors justify omission of the Morabit et al. 2021 ML agent by claiming that the expert they used provides an upper-bound on the best possible performance of the ML agent. While this is true in terms of decision quality, the ML agent of Morabit et al. 2021 should have a much faster solving time than that of the the 1-step-lookahead expert it imitates. Therefore, the authors should compare the solving time of RLCG to that of the ML agent of Morabit et al. 2021 - this should also enable more baselines than just greedy to be added to the VRPTW benchmark, which the authors claim is too computationally expensive to apply the 1-step-lookahead expert.\n\n    * In relation to the above, the authors might also consider comparing RLCG to the work of Shen et al. 2021 and Babaki et al. 2022. In particular, Shen et al. 2021 appear to compare their ML-for-CG agent to a more comprehensive set of CG solvers than those considered by the authors (e.g. see Fig 2 of their paper). Are such baselines not relevant to the authors’ RLCG work?\n\n* **Missing discussion of agent performance trend:** Why do the authors think in Fig 2 that the RL agent performs better than the expert in terms of number of iterations on the larger instances but not on the smaller instances (e.g. Fig 2a vs. Fig 2c)? This seems counter intuitive, since the expert is doing a 1-step lookahead regardless of the size of the problem, so I would have thought that the larger state-action space would have no effect on the expert but would present a familiar challenge for the RL agent. Is it really the case that this is down to longer episodes and therefore greater opportunity for non-myopic CG agents? Fig 2a already has episodes $40$-$80$ iterations long, which seems ample opportunity to outperform a 1-step lookahead policy. Would this indicate that, for some reason, non-myopic policies only have an advantage (in terms of decision quality) over myopic agents when making column selection decisions which can influence future selections $\\geq 200$ steps later?\n\n* **Curriculum learning analysis and discussion:** It is interesting that the authors emphasise the importance of curriculum learning on the final attainable results of RLCG. However, I do not fully follow the curriculum learning schedule or its effects described in the Appendix.\n    *  In Fig 7 of the Appendix, the authors label their figures as ‘learning curves’. However, this is confusing terminology; usually learning curves show how the agent performs as a function of the number of training iterations/epochs it has undergone. The authors have instead plotted the instance index on the x-axis. As such, this is not really a curve showing how the agent is learning during training, but rather a plot of the agent’s performance for each instance. Furthermore, it is not clear what Fig 7 is showing; when indexing the instances from easy to hard and then randomly indexing the instances, is it not obvious that the former will lead to an upwards trend and the latter will lead to a random noise graph? How does this show the influence of curriculum learning on the agent in terms of learning stability and/or final attainable performance? I think a simple validation plot showing the performance of the curriculum and w/o curriculum agents on the validation set as a function of learner epochs would be more useful and demonstrate the efficacy of curriculum learning.\n    * In Table 5 of the Appendix, the authors show how they split the instances into easy, medium, and hard instance types, but I cannot see what the curriculum schedule is in terms of when the agent progresses to the next level of difficulty. When does the agent move from easy to normal to hard? This should be carefully and clearly described given the claimed importance of curriculum learning.\n    * Finally, although not essential, if space allows I would consider moving some of the curriculum learning results and/or their analysis and discussion into the main paper.\n\n* **Analysis and discussion of proposed method's sensitivity to the introduced hyperparameter:** Does the sensitivity of RLCG to $\\alpha$ in the reward function change for different problem types? What is the advantage of having this explicit balancing between the two components of the reward function?\n\n\n### Miscellaneous minor issues\n\n* Pg 7 Fig 2: The figure text is too small to read.\n\n* Appendix pg 16 line 523 typo: ‘Similarly,the...’\n\n\n### References\n\n* Mouad Morabit, Guy Desaulniers, and Andrea Lodi. Machine-learning–based column selection for column generation. Transportation Science, 55(4):815–831, 2021.\n\n* Yunzhuang Shen, Yuan Sun, Xiaodong Li, Andrew Eberhard and Andreas Ernst. Enhancing Column Generation by a Machine-Learning-Based Pricing Heuristic for Graph Coloring. AAAI, 2022.\n\n* Behrouz Babaki, Sanjay Dominik Jena and Laurent Charlin. Neural Column Generation for Capacitated Vehicle Routing. AAAI ML4OR Workshop, 2022.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong points:\n* Considers an important application area of machine learning; improved column generation algorithms have the potential to address a variety of real-world continuous and discrete optimisation problems.\n* For the most part, the paper is excellently written and easy to follow.\n* The RL agent outperforms the brute-force 1-step-lookahead expert in terms of decision quality on larger instances, which is an impressive result.\n\nWeak points:\n* The related work is missing some key ML-for-CG references.\n* The experiments section lacks a comparison to any ML-for-CG agent despite multiple options being available in the literature.\n* The curriculum learning approach and results seem unclear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept