RL4CO: a Unified Reinforcement Learning for Combinatorial Optimization Library

Thanks for your thorough review and for acknowledging our contributions! We will address your concerns in the following answers.

The title of this paper is RL4CO, but it only addresses routing-related problems. Would it be more appropriate to name it RL4Routing?

RL4CO is not confined to routing problems only. In fact, Appendix B is about the decap placement problems from electronic design automation (EDA), which we did not include in the main text mainly because of space - given the practicality of the problem needed more background, we felt it would be better for EDA to be in a separate section of the paper.

Our goal is to include a wide variety of problems with the help of our community. For instance, we recently introduced the library scheduling problems including the Single Machine Total Weighted Tardiness Problem (SMTWTP) and the Flexible Flow Shop Problem (FFSP). Moreover, RL4CO is easily extensible to other problems; for instance, a recent paper [1r] has extended our implementation to the max cover problem and facility location, which we plan to integrate in RL4CO.

This paper […] implements various RL methods for these problems. However, at their core, these methods belong to the same category (and share very similar algorithm procedures), and there is a lack of insights to organize this category effectively. If this article could provide some useful conclusions or derive new methods based on these benchmarks, it would become novel.

Thanks for your insight! We suppose by the same category you mean autoregressive constructive methods for combinatorial optimization, i.e., that directly construct a feasible solution given a problem instance node-by-node. In terms of software organization, our fundamental insight is to divide and conquer the problems (in terms of data, environment, model, training) into more manageable subproblems. For instance, while several practical implementations in the NCO community separate different problems into separate schemes - one can think about different folders each with its own problem to solve but with mostly redundant code, that make management and progressive development hard, especially for new researchers - we decided to rely on unified structures. In the case of data, this was e.g. thanks to TensorDict, that allows for batched operations on named tensors, greatly simplifying passing around instances. In the case of environment, thanks to TorchRL we created a blueprint for vectorized CO environments that can run on GPU thus greatly alleviating the typical CPU simulation bottleneck typical of RL. As for the models, given common structures in the encoding-decoding architecture, we managed to modularize the policies as described in Figure 3.2, with the main idea being to abstract away problem-specific modules from common structures as encoder and decoder layers. For the training, we use PyTorch Lightning to reorganize the flow from input to output (in training, from data to loss function to optimize the parameter). Once again, many of these procedures are common among different RL algorithms (e.g. in A2C and REINFORCE with different baselines, this means modularizing the baselines). In terms of research, we have identified several pitfalls that can be encountered when training CO solvers, such as out-of-distribution generalization, that could be alleviated by introducing several inductive biases or exploring different directions as highlited in the paragraph “Future Directions in RL4CO” in Section 4.3. Finally, we believe the first steps in deriving a new methods is to recognize the problems as we highlighted in our benchmarking sections, and importantly, having a solid software base from which to start experimenting.

Thank you for your insightful feedback. We will answer to your concerns point by point.

Though the authors claim that they aim to propose a unified framework, the methods considered in their paper are mainly based on AM and POMO, in other words, the auto-regressive methods. As far as I know, there are also other methods other than auto-regressive, such as Local-rewrite[1]. Instead of constructing the solution from scratch, methods like Local-rewrite aim to improve an existing solution. Are these kinds of methods able to integrate into the proposed RL4CO framework?

You are correct. Indeed, RL algorithms for CO can be generally divided into 1) constructive and 2) improvement.

Constructive methods usually generate the solution from scratch, which we focus on in the paper. They are generally faster, but the quality of solutions can be lower than that of improvement methods. In construction methods, inference techniques (such as greedy multistart, sampling and augmentation) focus on getting the best out of several generated solutions, while search methods such as EAS focus on improving the quality of generated solutions efficiently by updating the model at test time.

On the other hand, improvement methods (such as the papers [1,2]) learn to improve existing solutions. Usually obtain a better solution, but are slower and may be less general (i.e. specialized to a class of problems such as routing). The reason why in RL4CO we focus first on construction methods is that they are more generally applicable to a wide variety of problems, such as routing and electronic design automation, while most learned improvement approaches are ad-hoc for a single class of problems, such as integer programming [2r] or routing problems [1r].

The proposed unified framework mainly focuses on TSP/VRP and the graph-based CO problems. However, there are other kinds of CO such as bin-packing, job scheduling, and mixed integer programming. I wonder if the proposed RL4CO covers these CO problems.

We agree with your opinion. We created RL4CO with not just routing problems in mind - for instance, as shown in Appendix B, we implemented electronic design automation. Our goal is to include a wide variety of problems with the help of our community. For instance, we recently introduced in the library scheduling problems including the Single Machine Total Weighted Tardiness Problem (SMTWTP) and the Flexible Flow Shop Problem (FFSP). Moreover, RL4CO is easily extensible to other problems; for instance, a recent paper [4r] has extended our implementation to the max cover problem and facility location, which we plan to integrate in RL4CO.

Thank you for your insightful review. We are glad you acknowledge the strengths of our paper and library, including reproducibility, usability, comprehensiveness, and presentation. We will address your concerns in the following.

This paper quite narrows the idea of RL algorithms for CO. There could be different ways to formulate the CO as an RL problem, not limited to the one outlined in Equation (1) - (3). For example, neighborhood search first constructs an initial feasible solution and optimizes the current solution at each step [1,2].

You are correct. Indeed, RL algorithms for CO can be generally divided into 1) constructive and 2) improvement.

Constructive methods usually generate the solution from scratch, which we focus on in the paper. They are generally faster but the quality of solutions can be lower than improvement methods. In construction methods, inference techniques (such as greedy multistart, sampling and augmentation) focus on getting the best out of several generated solutions, while search methods such as EAS focus on improving the quality of generated solutions efficiently by updating the model at test time.

On the other hand, improvement methods (such as the papers [1,2]) learn to improve existing solutions. Usually obtain a better solution, but are slower and may be less general (i.e. specialized to a class of problems such as routing). The reason why in RL4CO we focus first on construction methods is that they are more generally applicable to various CO problems, such as routing and electronic design automation, while most learned improvement approaches are ad-hoc for a single class of problems, such as integer programming [1] or routing problems [2r].

DIMES predicts a solution directly and optimizes the model with REINFORCE (one-step RL) [3] […] I note that DIMES is listed as a supervised approach (footnote on page 1), which I think is incorrect. I'm wondering if the authors have any specific criterion for the method classification or it is just a mistake (relevant to the first point in weaknesses).

About the mistake: yes, you are right, this is a typo on our side; thanks for spotting it! We have removed it from supervised approaches in the revised PDF.

About benchmarking DIMES: we agree with you; we would like to do this! However, we would like to remind that our method is more general regarding solvable problems, i.e., we can deal with more complex constraints. In DIMES, it unclear whether the approach can be extended to problems with more complex constraints; in fact, authors only mention possible extension to other NP-complete problems (i.e., quoting the authors, “extendable to NP-complete problems [1r]”), but not to NP-hard problems such as vehicle routing problems in general. This limits several practical applications of NCO, which involve several more complex constraints than the ones found MIS and TSP.

Most CO problems presented in the paper are routing problems, other classical CO problems like set covering, and maximum independent set are not covered.

We agree with your insight, it would be useful to have such problems covered as well in the future and we believe it will not be hard thanks to our design choices. Our goal is to include a wide variety of problems with the help of our community. For instance, we recently introduced the library scheduling problems including the Single Machine Total Weighted Tardiness Problem (SMTWTP) and the Flexible Flow Shop Problem (FFSP). Moreover, RL4CO is easily extensible to other problems thanks to its flexibility; for instance, a recent paper [3r] has extended our implementation to the max cover problem and facility location, which we plan to integrate in our library.

---

[1r] Richard M Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85–103, 1972.

[2r] Hottung, André, and Kevin Tierney. "Neural large neighborhood search for the capacitated vehicle routing problem." ECAI 2020 (2020).

[3r] Anonymous. “Unsupervised combinatorial optimization under complex conditions: Principled objectives and incremental greedy derandomization”. Under submission at ICLR (2024).

Thank you for your review. We would like to address the raised points below.

[…] there is no novelty. I understand that the paper is supposed to be a unified toolbox for the implementation and evaluation of AR methods for CO, but the research track of ICLR is intended for novel problems and/or solutions. In the spirit of that, I cannot recommend the paper for publication and suggest that the authors submit the work to a benchmarks or tool track

We believe the novelty of RL4CO does not lie in the fact that we introduce new problems and solutions but in the fact that we are the first to make problems and solutions that have been proposed easily accessible in a unified manner for quick and fair comparison. Our idea is that in such a way, new researchers and practitioners will be able to develop new algorithms or solve new problems in an organized manner, thus speeding up the research in the NCO community.

Further, historically, several libraries and benchmark papers have been accepted in ICLR, whose contribution relies mostly on the software aspect (for example, [1r, 2r, 3r]). While we do agree with you that the novelty in a classical “research track” sense may be limited mainly to pointing out flaws of existing methods and possible solutions, we believe the real novelty and contribution of RL4CO is to provide a tool that ultimately will empower research in this field.

We hope that in the future ICLR will offer a datasets and benchmarks track so that such works may be evaluated accordingly based on their contributions.

In your opinion, why do policy optimization methods seem to outperform value-based methods in neural CO?

In short: value-based methods have to learn to predict the reward for a given instance accurately, but for CO problems such as in routing, this is not an easy task, where small variations in decision-making can yield huge differences in the final reward. Moreover, the reward is sparse (i.e. we have to wait until the full solution has been decoded to know the value), which further hinders the accuracy of value-based methods.

We can further clarify the theoretical advantage of using policy gradients (PG) as REINFORCE methods over Actor-Critic (AC) methods in our setting. Accurately estimating $R(x,a)$ is important to train the NCO solvers with high performance. According to the estimation methods of $R(x,a)$, we can differentiate AC and PG. The AC methods (AM-PPO, AM-Critic) typically rely on the learned critics $V_\phi(x)$ to estimate $R(x,a)$ in the spirit of temporal-difference (TD) methods. TD methods can be sample-efficient and typically exhibit lower variance on estimating $R(x,a)$compared to PG. However, $V_\phi(x)$ is known to be a biased estimator of $R(x,a)$. On the other hand, the PG method estimates $R(x,a)$ via the Monte-Carlo method, which is known as an unbiased estimator of $R(x,a)$, instead can exhibit higher variance on estimating $R(x,a)$ than AC methods. Typically, our benchmarked algorithms, such as AM, POMO, and Sym-NCO, utilize proper baselines that can reduce the negative effect of larger variance on estimating $R(x,a)$. Furthermore, in NCO, generating training samples can be simpler than the other RL applications, as the rollout of the environment can be done simply by plugging in the constructed solution into the CO problem. Due to such reasons, in our benchmarked NCO settings, PG with a proper baseline (e.g., AM, POMO, Sym-NCO) tends to perform better than AC methods (e.g., AM-PPO, AM-Critic) while enjoying reduced variance and unbiased on estimating $R(x,a)$.

---

[1r] Rogozhnikov, Alex. "Einops: Clear and reliable tensor manipulations with einstein-like notation." ICLR2022 (2022)

[2r] Morad, Steven, et al. "POPGym: Benchmarking Partially Observable Reinforcement Learning." ICLR2023 (2023)

[3r] Choe, Sang Keun, et al. "Betty: An automatic differentiation library for multilevel optimization." ICLR2023 (2023)