Memory-Enhanced Neural Solvers for Efficient Adaptation in Combinatorial Optimization

Authors: Felix Chalumeau, Refiloe Shabe, Noah De Nicola, Arnu Pretorius, Thomas D Barrett, Nathan Grinsztajn
Primary area: reinforcement learning
Keywords: Reinforcement Learning, Combinatorial Optimization, TSP, CVRP

Abstract:
Combinatorial Optimization is crucial to numerous real-world applications, yet still presents challenges due to its (NP-)hard nature. Amongst existing approaches, heuristics often offer the best trade-off between quality and scalability, making them suitable for industrial use. While Reinforcement Learning (RL) offers a flexible framework for designing heuristics, its adoption over handcrafted heuristics remains incomplete within industrial solvers. Existing learned methods still lack the ability to adapt to specific instances and fully leverage the available computational budget. The current best methods either rely on a collection of pre-trained policies, or on data-inefficient fine-tuning; hence failing to fully utilize newly available information within the constraints of the budget. In response, we present MEMENTO, an approach that leverages memory to improve the adaptation of neural solvers at inference time. MEMENTO enables updating the action distribution dynamically based on the outcome of previous decisions. We validate its effectiveness on benchmark problems, in particular Traveling Salesman and Capacitated Vehicle Routing, demonstrating its superiority over tree-search and policy-gradient fine-tuning; and showing it can be zero-shot combined with diversity-based solvers. We successfully train all RL auto-regressive solvers on large instances, and show that MEMENTO can scale and is data-efficient. Overall, MEMENTO enables to push the state-of-the-art on 11 out of 12 evaluated tasks.

Decision: reject
Reviewer scores: 3, 3, 5, 3

Reviews and discussion:
<thread>
creation date:
1729509364777

thread_type:
official_review

<thread_object>
creator: reviewer_bp3q

<content>
summary:
The paper introduces MEMENTO, a novel memory-based approach designed to enhance existing constructive solvers for combinatorial optimization problems. MEMENTO leverages information from past solution attempts to improve the construction process, using a multilayer perceptron (MLP) network that takes features such as past actions, log-likelihood, and remaining search budget as input. This information is used to adjust the solution generation policy during inference, leading to higher-quality solutions within the given computational budget. The authors demonstrate that MEMENTO can improve the performance of base constructive models like POMO or COMPASS on problems such as the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP).

strengths:
Adapting the solution generation process using memory to account for previous attempts is undoubtedly a valuable and significant research direction.

weaknesses:
This paper introduces a 'meta-learning' approach in building solvers for combinatorial optimization problems, structured around two levels of machine learning. The lower-level learning takes place during inference, where previous solution attempts stored in memory are used to update the node selection policy. The upper-level (meta) learning, referred to as 'training' in the paper, involves training a multilayer perceptron (MLP) to find the optimal parameters that shape the behavior of the lower-level learning.

For the lower-level learning, I find the proposed method overly simplistic, with two primary issues.

First, the method indiscriminately utilizes all data in memory associated with the current node. Past experiences at the same 'current node' should not automatically be considered as occurring in the same 'state.' Although I haven’t thoroughly verified this, I believe the current implementation doesn’t necessitate storing the entire raw history. Instead, it could maintain only the accumulated 'logit correction values' and update them as new data arrives. In this sense, the term 'memory' may be too generous for the proposed approach, which feels closer to a simple bookkeeping method (EAS-tab) or basic active learning, both of which adjust the policy after each trajectory rollout iteration. A more effective memory system would incorporate mechanisms to retrieve the most relevant and important data while discarding irrelevant or potentially harmful data.

Second, the input features chosen for learning appear somewhat arbitrary. While the inclusion of the 'budget' feature is a helpful addition, many of the other features seem to offer limited value (as shown in Figure 9), and there is no clear theoretical basis for their usefulness. Moreover, generalizing these features to other combinatorial problems beyond fixed-sized routing may prove challenging.

Regarding the upper-level learning, the authors should provide a more precise and detailed explanation of their meta-learning approach, as applying meta-learning to combinatorial problems is an especially difficult task. To find a globally optimal solution using a reinforcement learning (RL) approach, an end-to-end method may be more suitable than optimizing over a few grouped trajectories, as done in this paper. To partly address this limitation, the authors manually adjust the learning process by logarithmically increasing the loss weight. An effectively designed RL approach would ideally discover optimal weights autonomously, eliminating the need for manual adjustments.

In addition to these concerns, the proposed method yields only marginal improvements over other baselines. Consequently, I believe the paper does not meet the high standards of ICLR.

questions:
I would like to understand the MLP structure used by the authors, described in Table 4.

Does "memory size 40, number of layers 2, hidden layers 8" imply the following MLP structure?

1) An input layer with 40 neurons
2) A first hidden layer with 8 neurons
3) A second hidden layer with 8 neurons
4) An output layer with 1 neuron
</content>
</thread_object>

</thread>
<thread>
creation date:
1730633329500

thread_type:
official_review

<thread_object>
creator: reviewer_r4rn

<content>
summary:
This paper proposes MEMENTO, a method for fast instance-specific adaptation in CO problems when a certain budget is allowed by utilizing a memory module. The proposed memory module is a lookup table storing information encountered during the online search process that is important for decision-making, such as the outcome of certain actions. This is then fed into an MLP, whose output modifies the action probabilities at each step. The method is evaluated in standard routing problems TSP and CVRP up to 500 nodes where it demonstrates SOTA results against RL-trained autoregressive solvers for CO.

strengths:
1. The paper is very well written and clear with relevant citations to previous literature.
    
2. The proposed MEMENTO module is novel and simple enough to be applied to a range of autoregressive CO solvers in the future, and thus, I believe it is an available addition to the NCO community.
    
3. Good overall performance (albeit with some concerns about baselines below) and experimental validation, including classical benchmarking, zero-shot combination with new solvers, and scaling to large sizes.
    
4. Code is provided, and authors make an effort to make their checkpoints available to the community.

weaknesses:
1. My biggest concern is about fairness in comparison with EAS. In particular, the values reported in the paper are worse than the ones in the original paper. For instance, for the Kool et al. (2019) 10k instances with 100 nodes, the value reported is 7.778 vs the original 7.769 for the TSP (MEMENTO: 7.768) and 15.66 vs 15.63 for the CVRP (MEMENTO: 15.65). Compared to the values reported in the original paper, MEMENTO would be worse than EAS. This holds true at larger sizes too. Do the authors have an explanation for this? 

2. MEMENTO is only applied to routing problems despite the title appealing to a broader “Combinatorial Optimization”. In this sense, experimenting with differently structured environments such as the Job Shop Scheduling (JSSP) as done in COMPASS and EAS would be beneficial.
    
3. When computing gaps, it would be best to do so compared to SOTA heuristic methods. For instance: in Figure 7, in Table (b), only LKH3 is reported, while HGS is much more powerful on CVRP. However, the authors do report HGS in the appendix, which obtains much better solutions than LKH. This also applies in particular to Table 1, where the “optimality gap” appears to be negative.
    
4. Given that only routing problems are considered in this paper, it would be beneficial to mention the additional work [1].

5. Some questions regarding hyperparameters remain, see below questions.
    

---

[1] Son, Jiwoo, et al. "Meta-sage: Scale meta-learning scheduled adaptation with guided exploration for mitigating scale shift on combinatorial optimization." International Conference on Machine Learning. PMLR, 2023.

questions:
1. What is the impact of the MLP in terms of cost? Since this has to be called each time, I wonder whether similar results could be obtained with a simple linear layer as well.
    
2. In Figure 2: MEMENTO’s logit update encourages with higher amplitude high-reward actions rather than low-return ones. Is this due to the `ReLU` applied to the reward, constraining it to be strictly positive? I wonder if this analysis would hold without such constraint.

3. Can your method be applied to broader problems that include e.g. edge features as the JSSP?
    
4. What is the impact of the memory size? Would increasing it be beneficial?

5. MEMENTO appears to be >$2\times$ slower than EAS at larger sizes as seen in Appendix A.1. Would EAS, provided with as much time budget as MEMENTO, eventually surpass the latter?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730737187559

thread_type:
official_review

<thread_object>
creator: reviewer_sd71

<content>
summary:
This paper introduces a fine-tuning method applied during inference to enhance construction methods for combinatorial optimization. It stores historical trajectories from fine-tuning as memory, which is processed by an MLP to adjust the original action probabilities. New solutions are then sampled from this memory-augmented distribution. The pretrained model and memory network are updated using an improvement reward based on the difference between the current solutions and the best-so-far solutions. Experiments are conducted on TSP and CVRP with problem sizes of 100 (generalizing to 125, 150, and 200) and 500.

strengths:
1. The source code is provided.
2. This work has the potential to enhance the pre-trained construction methods for TSP and CVRP.
3. The idea of reusing the historical trajectories (i.e. the memory) is interesting.

weaknesses:
1. Marginal Improvement: The improvement of MEMENTO over EAS appears marginal, especially when generalizing to larger scales (e.g., TSP200 in Figure 3). In the CVRP results, the improvement of MEMENTO is also not significant.
2. Scalability Concerns: In the larger-scale experiment (n=500), MEMENTO only slightly outperforms COMPASS, while introducing higher computational overhead.
3. Incomplete Literature Review: The literature review lacks coverage of works focused on scalability and generalization.
4. High Computational Cost of Fine-Tuning: The proposed fine-tuning method introduces additional computational overhead.
5. Missing Generalization Experiments: Would be useful to add some generalization experiments on different distributions.
6. Writing Quality: The writing lacks logical flow, and the table formatting needs improvement.

questions:
1. Why does POMO with sampling strategies perform worse than POMO with the greedy rollout when generalizing to N=200 in Figure 3?
2. Would it be feasible to apply MEMENTO to improvement methods as well? If so, are there any considerations that would impact its performance?
3. What's the inference time of the methods displayed in Figure 3? The bar chart results seem to replicate those in the table on the left, making it feel a bit redundant
4. Can MEMENTO be applied to other COPs? For example, I noticed that the code includes a preliminary implementation for the Knapsack Problem. I’d be interested to see the results and understand how MEMENTO might extend to different COPs.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730755192676

thread_type:
official_review

<thread_object>
creator: reviewer_yhms

<content>
summary:
The paper proposes a method (MEMENTO) for online fine-tuning of neural CO models. More concretely, MEMENTO learns the rules for updating the policy parameters at inference time. This is achieved by leveraging a learned residual policy for the base policy, where this residual policy utilizes the past solution predictions to explore the search space. Through experiments on the TSP and the CVRP, the paper demonstrates MEMENTO's efficacy against baseline methods.

strengths:
- The paper conveys most of the ideas clearly.
- The idea of leveraging a learned residual policy for online fine-tuning of the base policy at inference time is interesting and novel.

weaknesses:
- MEMENTO prevents the retrieval step from being too costly by only collecting data from the same node we are currently in. Could the authors elaborate on why this is a good retrieval strategy? Information should somehow be retrieved based on the partial solution constructed, since node-level decisions could be vastly different depending on the overall solutions.
- The experiments do not use augmentation with symmetries in the experiments, which they claim to be not critical by citing just one prior work (COMPASS). Overall, to claim that MEMENTO outperforms EAS, the authors should compare it against EAS with augmentation enabled since EAS has been shown to work better that way. 
- My main concern with this paper is regarding the runtime of different methods in the experiments (which aren't reported for the major experiments in the main paper and put in the appendices instead). In Appendix A.1, the authors clarify that they report the runtime to solve one instance rather than the entire dataset. Given this, the comparison is fair only if they give each algorithm the same amount of runtime. However, Table 2 in the appendices shows that MEMENTO takes more than 2x the runtime than COMPASS (more than 4x for CVPR-100). The runtime is significantly higher than that for EAS as well (more than 2x) for CVRP-100.
- The paper makes a few incorrect statements or claims:
         1. In the definition of $\pi^\star$ on Page 3, if we are taking a max over $i$, why does $i$ appear in the outer expectation?
         2. The claim that MEMENTO at least learns the REINFORCE update in the worst case is not exactly correct. In the worst case, the residual policy could output random values. I think the authors wanted to claim that the residual policy has the ability to at least learn the REINFORCE update rule (if nothing better). 
        3. The paper claims that MEMENTO  is "designed" to be agnostic to the base policy. While the authors demonstrate empirically that the learned residual policy for POMO could be used with COMPASS, the design of the framework as such makes the residual policy very much dependent on the base policy since they're learned jointly.

questions:
1. Could the authors suggest alternative strategies for retrieval that do consider the partial solution constructed?
2. Could the authors report the results with augmentation enabled?
3. Could the authors report the results with the same runtime allocated to each algorithm in the experiments?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732387690814

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We thank the reviewers for their comments and suggestions. We are pleased to see the contributions of our work highlighted, and are taking note of the feedback provided.

We reply to each reviewer independently. We hope that all raised points have been addressed and are willing to discuss any remaining concerns that the reviewers may have.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733170786977

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We would like to thank all reviewers for their initial comments. We thank R4rn and bp3q for engaging in discussions. We nevertheless regret that reviewers YhmS and Sd7 did not even acknowledge our answers, although addressing all their points and containing additional results on request.

Looking at the discussions, we believe to have addressed the main concerns raised by the reviewers.
- We provided details about the design choice of the retrieval process, showing that our final choice was well informed, and motivated by a crucial tradeoff between retrieval quality and computation cost.
- We provided an explanation to why we believe that the augmentation trick can be detrimental to assess NCO tools for search and planning. We have nevertheless provided these additional results, which confirms that MEMENTO outperforms EAS overall.
- We provided arguments to why using the runtime as a reference budget can induce biases; and have presented the comparative results of the standard benchmark using EAS’ runtime as reference, and confirmed that MEMENTO still leads the benchmark. We have also pointed the reviewers to the time scaling analysis that we provided in the paper (Fig. 7), which shows the promising scaling properties of MEMENTO. This should address all concerns regarding the runtime of MEMENTO.
- We also discussed all points raised by the reviewers, in particular a concern related to our work being a meta-learning study, and rectifying that our work is a contribution to the set of inference strategies that are available in the NCO toolbox. We re-iterate that MEMENTO fills an existing gap in the NCO literature; and provides clear empirical evidence for this.

In summary, we introduce a method that is described as novel and relevant by the reviewers, that is well motivated and positioned with respect to the existing literature. This method is thoroughly explained in the paper and implementation choices have been made in an informed way with respect to practical constraints. We have provided experimental evidence that the method fills a gap in the current state of NCO tools by proving that:
- it performs well on existing and new benchmarks: leads the standard benchmark with and without augmentation, leads the TSP500 benchmark, competitive on CVRP 500
- it scales well (TSP and CVRP 500), generalises well (TSP and CVRP 125, 150, 200), and can be combined with other solvers (MEMENTO + COMPASS zero shot combination)
- it is more versatile than existing alternatives: it works on a broad set of budgets whereas EAS struggles with instability, it can be applied to both TSP and CVRP whereas DIMES, MOCO, etc… cannot be applied to CVRP. 
- MEMENTO is introduced in a paper that also brings orthogonal contributions to the NCO literature: first study of the impact of the budget setting on methods’ ordering (Fig. 6), first effort to provide time scaling laws (Fig. 7), first time that POMO and COMPASS are trained on 500-size instances with RL, first methods trained on CVRP500 with RL, with code and checkpoints made available for future research.

Overall, our paper provides results, analysis, all material to reproduce results, but also checkpoints of our method and concurrent methods at scale that have never been reached before (POMO and COMPASS on TSP and CVRP 500). All in all, we believe to be making a significant contribution to the NCO literature and regret to see that this is not reflected in the current evaluation of the reviewers, with little elements to understand why.

We invite the reviewers to take one final look at the paper and the discussions, and to share their concluding thoughts on the contributions and merit of the work presented.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces MEMENTO, a memory-enhanced neural solver for combinatorial optimization, claiming improved adaptation and efficiency in tasks like TSP and CVRP. While the approach demonstrates promising performance compared to baseline methods, its novelty is unclear due to insufficient differentiation from existing work. Additionally, the experimental validation is narrow, lacking tests on a broader range of combinatorial problems, and the theoretical grounding of the memory-based adaptation mechanism is underdeveloped. These shortcomings, particularly the limited generalizability and unclear contributions, lead to the recommendation for rejection.