Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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).
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.

I 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.

Overall, everything looks solid in the paper and I believe this is a valuable contribution. I recommend this paper to be accepted.
questions: Minor suggestions related to clarity and details:

* 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.

* In Appendix C, it refers to the code for the network structure. Could you please describe the network structure in the appendix?

* Notes on text: Missing figure reference in line 176. Typo "hyperparemeters" in line 304. Some of the citations need to be with parenthesis.

I have a few questions that are not necessary for this submission, but mostly for my own curiosity:

1. 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.

2. 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.

3. 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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).
strengths_and_weaknesses: Strong points:
* 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.
* For the most part, the paper is excellently written and easy to follow.
* The RL agent outperforms the brute-force 1-step-lookahead expert in terms of decision quality on larger instances, which is an impressive result.

Weak points:
* The related work is missing some key ML-for-CG references.
* The experiments section lacks a comparison to any ML-for-CG agent despite multiple options being available in the literature.
* The curriculum learning approach and results seem unclear.
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.

* **Missing experimental baseline comparisons:** 

    * 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.

    * 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?

* **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?

* **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.
    *  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.
    * 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.
    * 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.

* **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?


### Miscellaneous minor issues

* Pg 7 Fig 2: The figure text is too small to read.

* Appendix pg 16 line 523 typo: ‘Similarly,the...’


### References

* Mouad Morabit, Guy Desaulniers, and Andrea Lodi. Machine-learning–based column selection for column generation. Transportation Science, 55(4):815–831, 2021.

* 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.

* Behrouz Babaki, Sanjay Dominik Jena and Laurent Charlin. Neural Column Generation for Capacitated Vehicle Routing. AAAI ML4OR Workshop, 2022.
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.  
strengths_and_weaknesses: Originality: 
This 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.

Quality: 
The 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.

Clarity: 
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.

Figure 2: The axes are very hard to read

Significance: 
It 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. 

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.

You 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?

How sensitive is the curriculum training process? Is it easy to build a curriculum? What happens if you do not use a curriculum?

For the Vehicle Routing problem, how does RL compare to MILPs?

Line 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.

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:

1.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.

2. 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.

3. 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strong:
* The application of RL to combinatorial optimization is a relevant research topic that gets more and more attention.
* The method outperforms the baseline on two relevant problems (cutting stock problem and vehicle routing problem with time windows).  
* I like Figure 1, it clarifies a lot. 
* You open source your code. 

Weak:
* See questions section. 
* 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. 
* 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. 
In 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.
questions: Questions:
* 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.   
* 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? 
* 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. 



Conclusion: 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: -
review_title: null

Meta-review: metareview: The reviewers all agree that the paper meets the acceptance bar.

At the same time, I would like to encourage the authors to seriously consider adding more experiments to the final paper as recommended by the reviews:
1. Given the motivation in the paper, the recommendation of Reviewer 8Csh about running some experiments for MIP is quite reasonable, and would make the story much more convincing. It would be a significant improvement, worth the extra software engineering efforts.
2. I do not quite agree with the reasons the authors rejected comparison with algorithms recommended by Reviewer Eksw. It was argued that these algorithms are superseded by the one-step lookahead algorithm. However, the latter is a greedy algorithm, while the ML based methods may deviate from it, which could be beneficial (especially, Babaki et al can try to learn a better sequential baseline if available). Some of these papers also consider adding multiple columns, as also suggested by Reviewer DMVD, and accepted as future work by the authors. Hence, comparison to these papers could partially answer that question.
3. Including the validation curves for curriculum learning as requested by Reviewer Eksw would also be quite interesting.

I sincerely hope that authors can run these experiments while preparing the final version.
confidence: Certain
Decision: Accept