Memory-Enhanced Neural Solvers for Efficient Adaptation in Combinatorial Optimization

W1: Node retrieval strategy.

We fully agree that the same node does not induce the same state and that ideally we would retrieve data based on similarity to the current partial solution. But this comes with a computation cost since it requires to get a similarity measure between the current solution and all the data points in the memory and then to extract the k most similar points. We observed that retrieving from the same node was an excellent proxy for similarity, and that the most similar points are very likely to come from the same node. This retrieval strategy hence provided a better tradeoff between quality and computation cost. This choice is discussed in the paragraph “retrieving data from the memory” (l. 200) but we are ready to extend it or to add details in the appendix if deemed necessary.

Please refer to Q1 from Reviewer YhmS for details about an alternative retrieval mechanism we actually ended up discarding in favor of our node retrieval.

W2: The current implementation could maintain only the accumulated 'logit correction values' and update them as new data arrives. The proposed approach feels closer to a simple bookkeeping method (EAS-tab).

Our method already has a similar behavior since the logit correction is stored with new data points. Hence at the next iteration the MLP can simply re-use the information as desired, or discard it (by using the “age” of the data, which tells how much of a shift might have happened). Having the capacity to discard it is a desired property since there is a policy shift happening.

The simple book-keeping method EAS-Tab uses a heuristic (“requiring deeper understanding of the CO problem”) to reinforce the probability to replicate the best found solution whereas our method uses a fully learned rule and can use 40 past solutions to inform the next iteration.

W3: Motivation for the memory input features, and generalization to other problems.

In section 3.2 and appendix F, we elaborate on the choice of those features. “Log probability” and “Return” are the core elements of a REINFORCE policy update. The “Log probability suggested by the memory” enables the accumulation of logit corrections over time. The “budget at the time the solution was built”, which can also be seen as the age of the data, enables to account for the distribution shift happening in the memory, i.e. giving more importance to recent data. The “Log probability of the entire trajectory” can be used to avoid discouraging an action that brought low return if that action was part of a trajectory that is believed to be unpromising anyway.

Those features are agnostic to the problem at hand, it hence should not be challenging to use them beyond TSP and CVRP. The only problem-size related one being the “Log probability of the entire trajectory”, which can either be normalized, or simply removed from the features. We can add those elements in the appendix of the paper.

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

The end-to-end approach would hardly work in this NCO setting. This would require learning how to extract relevant information from past attempts, in addition to learning how to re-use this information. The compute cost of the “extraction step” would typically be an order of magnitude more than the typical decoding step. At training time, it is unclear whether the computation graph would fit in memory, or would allow a big enough batch size to get stable gradients. At inference time, the method would be one or two orders of magnitude slower than the concurrent methods on the standard benchmark, and likely to have poor scaling properties.

Our final approach results from a compromise between learning as much as we can, and staying within the computation constraints imposed by the typical tasks that are considered in the NCO field currently.

W5: The proposed method yields only marginal improvements over other baselines.

For the sake of space, we refer the reviewer to our answer to W1 of Reviewer Sd71.

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

We apologize for the misprint in our hyperparameters table, “hidden layers” must be replaced by “hidden units”. To understand the MLP structure, let’s detail the process. Each memory entry has 7 associated features, which are processed by the MLP. The two hidden layers have 8 units. The output has a size of 1.

Hence the size of the MLP is [7, 8, 8, 1]. If the memory size chosen is 40, then the 40 entries are processed in parallel.. This is illustrated on Fig. 2 and described in the paragraph “processing data to update actions” of Section 3.2.

W1: Confusion with results reported in [1].

The discrepancy between those results comes from the use of problem augmentation using symmetries. It is a problem-specific trick that can only be used for a few CO problems. Additionally, most prior work assumes that this additional x8 batching can be achieved seamlessly, which is very unlikely in practice, when simulating complex real world scenarios.

Using this trick means decreasing the room for search and adaptation, since 87.5% of the budget is consumed to squeeze performance through uncontrolled network variance, rather than letting methods use principled strategies. Consequently, we genuinely believe that the NCO community would benefit from using a default evaluation setting that does not rely on this trick.

W2: MEMENTO is only applied to routing problems despite the title appealing to a broader “Combinatorial Optimization”.

We agree that adding another benchmark would strengthen the paper. Nevertheless, we decided to rather scale those environments to 500 nodes, which had never been done before and brought very interesting results. This effort was costly since we scaled all POMO, EAS, COMPASS and MEMENTO; and should be valuable to the community since we found unexpected rankings, plus we release the weights. We believe that this effort brings enough empirical evidence and justifies leaving other environments for future work. Since the design of our method makes it applicable to other COPs, we would like to keep the title that way, but are ready to reconsider this if this opinion is shared amongst all reviewers.

W3: Compute optimality gaps in comparison to SOTA heuristic methods, particularly HGS on CVRP large-scale.

We kept LKH3 as a reference since most of the methods we compare to report results with LKH3, and optimality gap cannot always be recomputed since only truncated results are given. We stayed consistent when moving to large-scale experiments. We are ready to update this if deemed necessary amongst the reviewers.

W4: Given that only routing problems are considered in this paper, mention additional work [3].

We thank the reviewer for pointing out recent work Meta-SAGE, which we will add to the related work section.

Q1: What is the impact of the MLP in terms of cost? Could it be replaced by a linear layer?

The MLP we use has 2 layers, with 8 hidden units. The computation has to be made for each memory entry sampled, which is 40 in most of our experiments. Those computations are done in parallel. Interestingly, this does not depend on the base architecture of the policy, hence this cost becomes negligible compared to the forward pass of the base policy when its size increases.

We have obtained better performance with a MLP compared to a linear layer, which we believe is explained by the fact that most rules we want to learn (i) require non-linearities (ii) can require interactive terms. Fig. 4 confirms that the learned rule is non-linear.

Q2: 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? Would this analysis hold without such constraint?

It is indeed linked to the ReLU used in the reward and it is a desired property. Removing the ReLU would mean optimizing for the average score obtained amongst the attempts rather than optimizing for the maximum.

Q3: Can your method be applied to broader problems?

Yes, MEMENTO’s pipeline is fully agnostic to the COP. The practitioner can tune the data retrieval strategy or add problem-specific information in the data features, but this is not a requirement for MEMENTO to work.

Interestingly, most concurrent methods that can be applied to TSP 500 (DIMES, MOCO, etc…) cannot be applied to COPs that cannot be expressed as heatmap; making them less applicable than MEMENTO.

Q4: Would EAS, provided with as much time budget as MEMENTO, eventually surpass the latter?

This really depends on the given problem, and time budget given, but also on the hardware accessible. For some of the experiments reported in the paper, it would likely be the case (for instance CVRP 125), but many others would not be affected (e.g. TSP results).

Additionally, the scaling laws reported on Fig. 7 show that for larger instances and larger networks, MEMENTO actually becomes faster than EAS, by a significant margin.

W1: Elaborate on why retrieving from the same node is a good strategy.

Ideally we would retrieve data based on similarity to the current partial solution. This comes with a computation cost since it requires getting a similarity measure and extracting the k most similar points in the entire memory. We observe that retrieving from the same node is an excellent proxy for similarity, and that the most similar points are very likely to come from the same node. This retrieval strategy hence provides a better tradeoff between quality and computation cost. This choice is discussed in the paragraph “retrieving data from the memory” (l. 200). We can extend it or to add details in the appendix if deemed necessary.

W2: Comparing MEMENTO against EAS with augmentation.

Augmentation with symmetries is a problem-specific trick that can only be used for a few CO problems. Most prior work assumes that this additional x8 batching can be achieved seamlessly, which is unlikely in practice, when simulating complex real-world scenarios. Using this trick means decreasing the room for search and adaptation, since 87.5% of the budget is consumed to squeeze performance through uncontrolled network variance, rather than letting methods use principled strategies. Consequently, we genuinely believe that the NCO community would benefit from using an evaluation setting that does not rely on this trick.

W3: Giving each algorithm the same amount of runtime to solve one instance.

Expressing the budget in terms of runtime (rather than attempts) is an interesting angle to take but has some limitations, which explain why it is not used as the reference budget in the literature: (i) different labs use different implementations and frameworks (ii) labs have access to different hardwares (iii) time is sensitive to parallelism, whereas number of attempts is not. Hence, comparing methods with time is subject to a higher number of biases, and would make it almost impossible to compare papers without a common codebase and hardware.

Nevertheless, our experimental section takes a step towards those additional time analysis since we provide on Fig. 7 the time scaling laws of MEMENTO and EAS, with respect to instance size and network size (expressed in number of deep layers).

W4: if we are taking a max over i, why does i appear in the outer expectation?

We kept the outer expectation term to emphasize the difference with the usual RL objective written line 133. We nevertheless agree that the formula can be simplified and will clarify this in the paper.

W5: Incorrect claim that MEMENTO at least learns the REINFORCE update in the worst case.

Line 185 states that “MEMENTO has capacity to at least rediscover REINFORCE”, which just implies that the REINFORCE update is contained within the space of what MEMENTO can learn. We nevertheless agree that line 225 can be confusing and we will fix it. Our results show that MEMENTO is indeed able to learn a REINFORCE-like update, with superior performance.

W6: Claim that MEMENTO is "designed" to be agnostic to the base policy.

We agree that there is a degree of interdependence (of the learned checkpoint) towards the base policy used at train time. But the learning process itself is mostly agnostic to the base policy: any other architecture than POMO could have been used since the adaptation mechanism of MEMENTO acts on the action distribution directly, whereas others act on an architecture-specific element of the base policy (like EAS-Emb, EAS-Lay and FER). Despite having been learned with POMO as a base policy, the fact that MEMENTO’s update rule can be zero-shot transferred to COMPASS shows that this degree of interdependence is small.

Q1: Could the authors suggest alternative strategies for retrieval that do consider the partial solution constructed?

The output of the multi-head attention of POMO’s decoder builds a low-dimensional representation of the partial solution. One can store this vector in the memory, and when building a new solution, retrieve only the k-nearest neighbors of the current partial solution’s representation. One could even apply further dimensionality reduction to reduce the cost of the nearest neighbor search.

This approach brings a significant cost increase, even when using state-of-the-art approximated nearest neighbor JAX implementation. This effect gets worse when batching the attempts, or the problem instances. Our simplified retrieval approach maintains similar results, while significantly improving scaling. We will add this information to the paper.

Q2: Could the authors report the results with augmentation enabled?

As discussed in our answer to W2, we believe that using 87.5% of the budget for this trick is not the right way to assess the search and adaptation capacity of NCO tools. We hence advocate not to use this trick to compare methods.

We have some additional data to share with the reviewer, concerning the results of the benchmark with the time used as budget. We still advocate for a moderate use of these results since they suffer from the bias discussed in our first answer, but we still believe that they give an interesting perspective on the methods.

We used EAS runtime as the reference time, and obtained the following results:

We observe that MEMENTO still leads the benchmark, with 6 out of 8 top results; and both methods are very close on the two tasks where EAS leads.

We still want to reiterate that this setting is the one where the time difference between EAS and MEMENTO is the largest, and when looking at larger instances and larger networks (right panel on Fig. 7), MEMENTO actually becomes faster than EAS.

We hope that these additional results resolve the reviewer’s concerns regarding the time efficiency of MEMENTO.

W1: The improvement of MEMENTO over EAS appears marginal.

The improvement of MEMENTO over EAS can appear marginal given how close methods are to optimality, in particular on the standard TSP/CVRP-[100-200] benchmark, but is still significant and in the typical magnitude observed in published NCO methods, and consistent over 11 of the 12 tasks. Furthermore, the standard benchmark uses a budget introduced by EAS, but Fig. 6 shows that for a wide range of other budgets, the gap between those methods can actually increase by a large margin.

Finally, a key message from our paper is that there is not any single NCO approach that is uniformly best; rather it depends on the setting (e.g. one vs few vs many shots, sequential solution attempts vs parallel decoding etc).

W2: Slight improvements of MEMENTO over COMPASS on larger-scale with a higher computational overhead.

In all the large-scale experiments, adding MEMENTO over COMPASS provides more than 10% decrease of the gap to the reference industrial solver, which corresponds to a significant improvement in the field of NCO.

W3: The literature review lacks coverage of works focused on scalability and generalization.

We have focused our literature review on the most important context of our contribution, while trying to stay concise. If the reviewer can point us to the papers that seem important, we are happy to add the closest ones to the main paper, and the others to a new dedicated section in the appendix.

W4: Computational overhead introduced by the fine-tuning method.

Any method that searches and/or adapts will come with a computational overhead. Storing data, creating a structure to aggregate it, updating parameters, processing data to compute an action distribution, etc… All those steps that are required for popular adaptation and search methods (tree search - SGBS, RL fine-tuning - EAS, learned policy update - MEMENTO) and consequently impact the tradeoff between the quality of the solutions produced, and the number of solutions that can be produced in a given time.

The interest of a method over another will depend on the budget available, the hardware available and many other factors. We provide empirical evidence in our paper that MEMENTO achieves the best performance in a range of settings, and does so with a significant margin. Additionally, we provide additional analysis that can help any practitioner to understand when it is appropriate to use MEMENTO over another method: the budget plot (Fig. 6) and the time scaling laws (Fig. 7). To the best of our knowledge, we are the first to shed light on those properties of neural solvers, and believe that this will ease transparency over strength and limits of the different NCO tools available to a practitioner.

W5: Add some generalization experiments on different distributions.

We would like to emphasize that TSP/CVRP with instance sizes 125, 150 and 200 are generalization experiments since methods were only trained on instances of size 100. Hence, our paper already provides 6 tasks out-of-distribution, confirming that MEMENTO is robust to distribution shift.

W6: The writing lacks logical flow.

Could the reviewer be more precise about the lack of logical flow? We are surprised to see this aspect of the paper underlined as a weakness and the score assigned for the presentation, given that other reviewers acknowledged its quality.

Q1: Why does POMO with sampling strategies perform worse than POMO with the greedy rollout when generalizing to N=200?

The runs of POMO with sampling use a temperature of 1 to sample from the action distribution (we re-use runs from the literature). The resulting noise increases with the size of the sequence of actions to take; hence becoming detrimental for instances of size 200, and only constructing solutions that are worse than the greedy rollout.

Q2: Would it be feasible to apply MEMENTO to improvement methods?

As MEMENTO is model-agnostic, we believe that improvement methods would also benefit from MEMENTO. We will outline this direction in our conclusion.

Q3: What's the inference time of the methods displayed in Figure 3? Redundancy on Fig. 3.

The value reported on the bar chart is an improvement over POMO greedy rollout (in %). There is some redundancy between the table and the bar plot, but we believe that it provides an efficient summary of the table.

Q4: Can MEMENTO be applied to other COPs?

Yes, MEMENTO’s pipeline is fully agnostic to the COP. The practitioner can tune the data retrieval strategy or add problem-specific information in the data features, but this is not a requirement for MEMENTO to work.

Interestingly, most concurrent methods that can be applied to TSP 500 (DIMES, MOCO, etc…) cannot be applied to COPs that cannot be expressed as heatmap; making them less applicable than MEMENTO.