Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a new method of updating deep neural networks for
combinatorial optimization problems during search using reinforcement learning.
In particular, the authors show that by updating only part of the network,
better results can be achieved at lower cost. They describe and evaluate their
method on different combinatorial optimization problems, comparing to other
machine-learning-based approaches as well as "traditional" solvers.
main_review: The paper presents an interesting idea that seems to have a large impact. The
evaluation is thorough and fair, the results are convincing. This is a good
paper that should be accepted.

There are a few minor points that were unclear to me and might warrant further
discussion. The results for the TSP in Table 1 show that concorde is often the
fastest solver. This is somewhat counter-intuitive, especially compared to LKH,
as it is a complete solver. The proposed method is also often much slower. Some
explanation of this would be helpful for the reader to understand what exactly
is going on there.

The most nebulous part of the proposed method to me is the placement of the new
layer, which sounds like it might be quite difficult in practice and potentially
require expensive evaluation of different alternatives. A more in-depth
discussion of how the authors determined this for their experiments, along with
some recommendations on how to do this in a new setting, would make the paper
stronger and more applicable in practice.

summary_of_the_review: Interesting method with promising results.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper deals with end-to-end learning of heuristics for combinatorial optimization problems. The authors propose an extension of the active search method of [Bello et al 2016], where only part of the model parameters are updated at test time for each instance. They propose three ways of applying this idea that consist in fine-tuning part of the instance embeddings, the parameters of an additional layer or directly the prediction scores of the model. Applied to the POMO method [Kwon et al 2020] for the TSP and CVPR and the L2D method of [Zhang et al 2020] for the JSSP, the proposed efficient active search leads to significant improvements on instances of the same size and larger than the training ones.

main_review: **Strengths**

1. The paper is clear, well organised and well written 
1. The presented approach seems applicable to any constructive method as long as it has a encoder/decoder type of architecture 
1. In the experiments, the proposed approach is applied to 2 models for solving 3 different problems and the results are consistently positive, which hints at the generality of the proposed approach. 
1. It improves the performance of the underlying model on test instances from the same distribution as the training instances as well as to larger instances (from the same distribution), effectively addressing the well-known difficulty of standard learning-based models to perform well on larger instances 
1.Nice discussion in Sec 4.4. to explain possible reasons of why one of the proposed variants work best for each problem. 

**Weaknesses**
1. In the experiments, the scale of instances is limited: 200 nodes for TSP and CVRP, while recent learning-based methods such as the cited [Fu et al 2021] manage to solve TSP instances with up to 10,000 nodes.
1. Generalisation is only illustrated (and claimed) with respect to the size of the instances. It would be interesting to see the results on other distributions shifts (e.g. applying EAS to a model trained on TSP100 on instances of TSPlib)
1. For CVRP, results are indeed provided for other distributions. But for each family of instances, the authors say that the model is trained for 3 weeks and then tested on similar instances for each family. Could EAS be helpful to learn good solutions starting from the same model?


**Recommendation**

I would vote for accepting the paper. The contribution is interesting as a middle ground between fine-tuning a whole model for each instance (active search) and other non-learning based search strategies (beam-search, sampling, etc). The proposed approach is illustrated on 2 models for 3 standard CO problems and consistently shows good results.

**Questions**
1. What is the motivation of adding a new layer to fine-tune (EAS-Lay) versus fine-tuning some existing layers of the model?
1. In Tables 1 and 2, why are there no entries for most of the learning-based baselines for N >= 125 ? Since there is no strict time-limit in this setting, I guess with a small-enough batch size for the models to fit into memory, all these methods would provide some results for N up to 200.
1. In Appendix Table 4, have you tried simply applying EAS to the model trained on the uniform distribution CVRP100? That would be a natural test of the  impact of EAS on generalization. 
1. Looking at Figure 3,  it seems the value of the best lambda depends on the problem and the range of potential values is quite wide (0,01-100). Have you checked the scale of the different losses and could it help explain such a difference?
1. If one were to apply EAS to another model/CO problem, could you deduce from your experiments a general kind of rule of thumb of which variant would work better for which situation?


**Additional feedback**
* In Introduction
    *  “these methods do not react towards the solutions seen so far, i.e., the underlying distribution from which instances are sampled is never changed throughout the search”. Not clear to me. Do you mean …from which solutions are sampled?
    * “..wide adaption” —> adoption
* Sec 3.Background: the decoder is introduced with parameter $\omega$, but this one is only defined as the embeddings in the next paragraph 
* Sec 3.1: In the definition of the total gradient right after equation (2), shouldn’t there be a minus before one of the gradients?  Since one gradient corresponds to the minimisation of the cost and the other to the maximisation of the likelihood.
* Figure 2: y-axis is the average costs. Optimality gap would be more relevant (and consistent) especially if instances have different sizes
* 



summary_of_the_review: The paper provides an interesting contribution to learn to search for high-quality solutions at test time, nicely completing end-to-end learning pipelines for solving CO problems. The proposed approach could be applied to any model that has an encoder-decoder type of architecture, and is experimentally validated on 2 models and 3 problems. A limitation is that it is not clear if it could help a model generalize to instances that are much larger than the training ones, or with significantly different characteristics. I vote for accepting the paper.


### Update after rebuttal

I thank the authors for precisely answering all my questions and concerns.
I am happy to confirm my initial recommendation of accepting the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies machine learning-based methods for combinatorial optimization. The paper builds upon Bello et al. (2016) on using reinforcement learning to generate solutions for combinatorial optimization problems (e.g., TSP). The novelty of the paper is to optimize only a subset of the model parameters. The paper then proposes three different implementations based on this idea.
main_review: Significance: One limitation of existing RL-based approaches for combinatorial optimization is its resource requirement. As demonstrated in Table 1, the active search technique in Bello et al. (2016) takes 5 days to solve 10,000 test instances of TSP. The paper aims to tackle this limitation by proposing to optimize only a subset of the model parameters. I think the paper is making a good and meaningful contribution towards research in the field.

Novelty: The paper extends the active search method in Bello et al. (2016). The three proposed implementations are based on one general idea of optimizing only a subset of the model parameters. The novelty of the proposed technique is therefore limited. However, if the method performs well, its simplicity could be of high interest.

Presentation: The paper is well-written. The related literature is discussed in detail. The experimental results are clearly presented, with ablation study and trajectory analysis. There are some minor ambiguities in presenting the proposed techniques, as elaborated below.

There are some ambiguities in the paper:

1. On page 4, below figure 1, the paper proposes the first strategy: update the embedding of the using the loss function J_{RL} and J_{IL}. These loss functions are not explicitly specified anywhere in the paper. Only their gradient w.r.t. the embeddings are presented in Eq.(1) and Eq.(2). Readers who are not familiar with RL/Imitation Learning literature may not know what J_{RL} and J_{IL} are. It would be great if the author can be more explicit about the loss functions before presenting their gradients.

2. In Table 1, the authors provide wall-clock time for the proposed algorithms and other baselines on a set of 10,000 TSP instances. EAS achieves competitive performance while taking only 5-7 hours to run, as compared to 5 days using the original active search. Is this improvement due to:
(a) EAS uses less memory, and hence we can solve more instances in parallel, or
(b) EAS is computationally more efficient, i.e., it uses less CPU-time to achieve the competitive performance, or
(c) a combination of the above?
It would be better if the authors report the CPU-time (instead of wall-clock time), and separately report the space (memory) and time (CPU) of these algorithms.

Minor comments:
In figure 3, the x-axis should be labeled lambda.

summary_of_the_review: The paper proposes a simple extension to an existing RL-based method for combinatorial optimization. Its effectiveness is demonstrated empirically. However, I feel that the results of the experiments should be reported in greater detail, i.e., to compare with the original active search in different performance metrics such as memory and CPU time usage.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies deep learning methods for solving combinatorial optimization problems. The authors write that state-of-the-art methods typically use models that consist of encoder and decoder units. The methods first create an embedding of the problem instance using the encoder. Then, starting with an empty solution to the problem, the embedding and the decoder are used to autoregressively construct a solution over a series of time steps. Given an already trained model and a test instance, this paper studies how to quickly update the model parameters in order to improve the quality of the solution returned by this procedure. The authors propose three techniques, which adjust (1) the normally static embeddings of the problem instance that are generated by the encoder model, (2) the weights of additional instance-specific residual layers added to the decoder, and (3) the parameters of a lookup table that directly affect the probability distribution returned by model.
main_review: Strengths:
- This paper studies an exciting area—machine learning for combinatorial optimization—where machine learning has the potential to make a big impact.
- From the experiments (especially Tables 1 and 2), it looks as through the proposed approaches are much faster than competitor, active search [Bello et al. ‘16], which (from my understanding) searches for ways to adjust all parameters of the trained model at test time. In contrast, the proposed approach only searches for ways to adjust specific subsets of model parameters, which makes the approach faster.
- I appreciate that the authors evaluate their approach on a few different types of combinatorial optimization problems: two different types of routing problems and a scheduling problem. For the scheduling problem, the improvement over active search is a bit more modest.

Weaknesses:
- I found the problem description somewhat hard to follow. In Section 3, it would be helpful to clarify what exactly an “action” corresponds to in this setting. One way to do this would be to summarize the combinatorial problems studied in the experiments section and explain what an action corresponds to and what the state $s_{t+1}$ corresponds to after applying an action $a_t$. 
- In terms of solution quality, the improvements over problem-specific baselines are sometimes really small (e.g., in Tables 1 and 2, a fraction of a percentage). On such a small scale, I wasn’t sure if I could trust the superiority of any particular method. Confidence intervals would really help here.

Detailed comments:
- Page 2: I’m not sure that “exemplary” is the right word here; I would remove it.
- Equation (1): I’m not sure what you mean when you say that $b_0$ is a baseline used to reduce variance. Can you say more?
summary_of_the_review: Overall, I’m leaning toward acceptance because the proposed approach seems to provide a notable improvement over prior methods (in particular, active search by Bello et al. ‘16]) in terms of runtime.
review_title: null

Meta-review: This paper gives a framework for using learning in combinatorial optimization problems.  In particular, active search is used to learn hueristics. The reviewers thought the paper had nice conceptual contributions for this approach and that the results would be very interesting to the community.
Decision: Accept (Poster)