Efficient Active Search for Combinatorial Optimization Problems
Authors: André Hottung
Yeong-Dae Kwon
Kevin Tierney
Venue: ICLR 2022 Poster (2022)
Keywords: heuristic search
combinatorial optimization
learning to optimize
reinforcement learning
traveling salesperson problem
vehicle routing problem
job shop scheduling problem

Abstract: Recently numerous machine learning based methods for combinatorial optimization problems have been proposed that learn to construct solutions in a sequential decision process via reinforcement learning. While these methods can be easily combined with search strategies like sampling and beam search, it is not straightforward to integrate them into a high-level search procedure offering strong search guidance. Bello et al. (2016) propose active search, which adjusts the weights of a (trained) model with respect to a single instance at test time using reinforcement learning. While active search is simple to implement, it is not competitive with state-of-the-art methods because adjusting all model weights for each test instance is very time and memory intensive. Instead of updating all model weights, we propose and evaluate three efficient active search strategies that only update a subset of parameters during the search. The proposed methods offer a simple way to significantly improve the search performance of a given model and outperform state-of-the-art machine learning based methods on combinatorial problems, even surpassing the well-known heuristic solver LKH3 on the capacitated vehicle routing problem. Finally, we show that (efficient) active search enables learned models to effectively solve instances that are much larger than those seen during training.

Published as a conference paper at ICLR 2022
EFFICIENT ACTIVE SEARCH FOR COMBINATORIAL OPTIMIZATION PROBLEMS
André Hottung
Yeong-Date Kwon Samsung SDS, Korea y d. kwwn@s com
Bielefeld University, Germany
andre. hot.tungeuni -bieeeeeedddllll..dddddd..
Kevin Tierney
Bielefeld University, Germany kevin. tierney@uni -ttp///nnd--ieleeeddddd.
ABSTRACT
Recently, numerous machine learning based methods for combinatorial optimiza- tion problems have been proposed that learn to construct solutions in sequential decision process via reinforcement learning. While these methods can be easily combined with search strategies like sampling and beam search, it is not straight- forward to integrate them into a high-level search procedure offering strong search guidance. [Bello et al. (2066) propose active search, which adjusts the weights of (trained) model with respect to a single instance at test time using reinforcement learning. While active search is simple implement, it not competitive with state-of-the-an methods because adjusting all model weights for each test instance is very time and memory intensive. Instead of updating all model weights, we propose and evaluate three efficient active search strategies that only update a subset of parameters during the search. The proposed methods offer a simple way to significantly improve the search performance of given model and outperform state-of-ther art machine learning based methods on combinatorial problems, even surpassing the well-known heuristic solver LKH3 on the capacitated vehicle routing problem. Finally, we show that (efficient) active search enables learned models to effectively solve instances that are much larger than those seen during training.
INTRODUCTION
In recent years, wide variety of machine learning (ML) based methods for combinatorial optimiza- tion problems have been proposed (e.g.. Kool et al. (2019); |Httung et al. (2020)).. While early approaches failed outperform traditional operations research methods, the gap between handcrafted and learned heuristics has been steadily closing. However, the main potential of ML-based meth- ods lies not only in their ability outperform existing methods, but in automating the design of customized heuristics in situations where no handcrafted heuristics have yet been developed. We hence focus on developing approaches that require as little additional problem-specific knowledge as possible.
Existing ML based methods for combinatorial optimization problems can be classified into con- struction methods and improvement methods. Improvement methods search the space of complete solutions by iteratively refining given start solution. They allow for guided exploration of the search space and are able to find high-quality solutions. However, they usually rely on problem- specific components. In contrast, construction methods create a solution sequentially starting from an empty solution (i.e., they consider search space consisting of incomplete solutions). At test time, they can be used to either greedily construct a single solution or to sample multiple solutions from the probability distribution encoded in the trained neural network. Furthermore, the sequential solution generation process can be easily integrated into a beam search without requiring any problem-specift components. However, search methods like sampling and beam search offer no (or very limited) search guidance. Additionally, these methods do not react towards the solutions seen so far, i.c., the underlying distribution from which solutions are sampled is never changed throughout the search.

---

Published as a conference paper at ICLR 2022
Bello et al. (2016) propose generic search strategy called active search that allows extensive, guided search for construction methods without requiring any problem specific components. Active search is an iterative search method that at each iteration samples solutions for single test instance using a given model and then adjusts the parameters of that model with the objective to increase the likelihood of generating high-quality solutions in future iterations. They report improved performance over random sampling when starting the search from an already trained model. Despite promising results, active search has not seen adaption in the literature. The reason for this is its resource requirements, as adjusting all model parameters separately for each test instance is very time intensive, especially compared to methods that can sample solutions multiple different instances in one batch.
We extend the idea of active search as follows. (1) We propose to only adjust a subset of (model) parameters to a single instance during the search, while keeping all other parameters fixed. We show that this efficient active search (EAS) drastically reduces the runtime of active search without impairing the solution quality. (2) We implement and evaluate three different implementations of EAS and show that all offer significantly improved performance over pure sampling approaches.
In our EAS implementations, the majority of (model) parameters are not updated during the search, which drastically reduces the runtime, because gradients only need to be computed for a subset of model weights, and most operations can be applied identically across a batch of different instances. Furthermore, show that for some problems, EAS finds even better solutions than the original active search. All EAS implementations can be easily applied to existing MI. construction methods.
We evaluate the proposed EAS approaches on the traveling salesperson problem (TSP), the capacitated vehicle routing problem (CVRP) and the job shop scheduling problem (ISSP). For all problems, we build upon already existing construction approaches that only offer limited search capabilities. In all experiments, EAS leads to significantly improved performance over sampling approaches. For the CVRP and the JSSP, the EAS approaches outperform all state-of-the-arg ML based approaches, and even the well-know heuristic solver LKH3 for the CVRP. Furthermore, EAS approaches assists in model generalization, resulting in drastically improved performance when searching for solutions to instances that are much larger than the instances seen during model training.
2 LITERATURE REVIEW
Construction methods Hopfield 1982) first used a neural network (a Hopfield network) to solve small TSP instances with up to 30 cities. The development of recent neural network architectures has paved the way for ML approaches that are able to solve large instances. The pointer network architecture proposed by VVinyals et al. (015)) efficiently learns the conditional probability of a permutation of a given input sequence, e.g., permutation of cities for TSP solution. The authors solve TSP instances with up to 50 cities via supervised learning. Bello et al.; (2016) report that training pointer network via actor-critic RL instead results in better performance on TSP instances with 50 and 100 cities. Furthermore, graph neural networks are used to solve the TSP, e.g., graph embedding network in Khalil et al. (2017) and graph attention network in Deudon et al. (2018).
The first applications of neural network based methods to the CVRP are reported by Nazari et al. (2018) and a recurrent neural network (RNN) decoder that can be trained via actor-critic RL. Kool et al. (2019) propose an atlention model that uses an encoder that is similar the encoder used in the transtormer architecture Vaswani et al. (201)). [Png et al. (219)) and Xin et al. (2021) extend the attention model to update the node embeddings throughout the search, resulting improved performance at the cost of longer runtimes for the CVRP. Falkner & Schmidt-Thiene
| Kool et al. (2019). Nazari al. (2018) propose model with an attention mechanism and
(2020) propose an attention-based model that constructs tours in parallel for the CVRP with time windows.
While ML-bbsed construction methods have mainly focused on routing problems, there are some notable exceptions. For example, Khalil et al. (2017) use a graph embedding network approach to solve the minimum vertex cover and the maximum cut problems (in addition to the TSP). Zhang et al.) (2020) propose graph neural network based approach for the job shop scheduling problem (JSSP). Li et al. (2018) use guided tree search enhanced ML approach to solve the maximal independent set, minimum vertex cover, and the maximal clique problems. For a more detailed review of ML methods on different combinatorial optimization problems, refer to Vesselinova al. 2020
2

---

Published as a conference paper at ICLR 2022
While most approaches construct routing problem solutions autoregressively. some approaches predict a heat-map that describes which edges will likely be part of a good solution. The heat-map is then used in a post-hoc search to construct solutions. Joshi et al. (2019) use graph convolutional network to create a heat-map and a beam search to search for solutions. Similarly, Hu et al. (2020) use a graph convolutional residual network with Monte Carlo tree search solve large TSP instances. [ooo iet al. (2021) use the model from Joshi et al. (011)) to generate the heat-map and use it to search for solution to TSP and CVRP instances with a dynamic programming based approach.
Improvement methods Improvement methods integrate ML based methods into high-level search heuristics or try to learn improvement operators directly. In general, they often invest more time into solving an instance than construction based methods (and usually find better solutions). [Chn & Tian (2019) propose an approach that iteratively changes local part of the solution. At each iteration, the trainable region pieking policy selects part of the solution that should be changed and trainable rule picking policy selects an action from a given set of possible modification operations. [Hotung & Tierney (2020) propose method for the CVRP that iteratively destroys parts of solution using predefined, handcrafted operators and then reconstructs them with a learned repair operator. Wu et al. (2021) and de O. da Costa et al., (2020) propose to use RL to pick improving solution from a specified local neighborhood (e.g., the 2-Opt neighborhood) to solve routing problems. |Hottung al. (202T) learn continuous representation of discrete routing problem solutions using conditional variational autoencoders and search for solutions using a generic, continuous optimizer.
SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS WITH EAS
We propose three EAS implementations that adjust small subset of (model) parameters an iterative search process. Given already trained model, we investigate adjusting (1) the normally static embeddings of the problem instance that are generated by the encoder model, (2) the weights of additional instance-specifie residual layers added to the decoder, and (3) the parameters of a lookup table that directly affect the probability distribution returned by model. In each iteration, multiple solutions sampled for one instance and the dynamic (model) parameters are adjusted with the goal of increasing the probability of generating high quality solutions (as during model training). This allows the search to sample solutions of higher quality in subsequent iterations, i.e., the search can focus on the more promising areas of the search space. Once a high-qualig solution for an instance found, the adjusted parameters are discarded, so that the search process can be repeated on other instances. All strategies efficiently generate solutions to batch of instances in parallel, because the network layers not updated during the search are applied identically to all instances of the batch.
Background RL based approaches for combinatorial problems aim to learn neural network based model Pa (TT (1) with weights 0 that can be used to generate solution и given an instance I. State-of- the-art approaches usually use a model that consists of an encoder and a decoder unit. The encoder usually creates static embeddings w that describe the instance / using a computationally expensive (col encoding process (e.g., Kool et al. (2019); Kwon et al. (2020). The static embeddings to autoregessively construct solutions using the decoder over T time steps. At each step f, the decoder (a) st, W), with weights ø O, outputs a probability value for each possible action in the state 8t (e.g.. for the TSP, each action corresponds to visiting a different city next). The starting state 81 describes the problem instance (e.g., the positions of the cities for the TSP and the starting city) and the state 1 is obtained by applying the action ae selected at time step to the state 8t. The (partial) solution F defined by the sequence of selected actions 01 02...., ag Once a complete solution, Tr, fulfilling all constraints of the problem is constructed, the objective function value C(T, 1) of the solution can be computed (e.g.. the tour length for the TSP).
then used
Figure I shows the solution generation for a TSP instance with a model that uses static embeddings. The static embeddings w are used at each decoding step to generate a probability distribution over all possible next actions and the selected action is provided to the decoder in the next decoding step. During testing, solutions can be constructed by either selecting actions greedily or by sampling each action according to (g(a|s,, w). Since the static embeddings are not updated during solution generation they only need to be computed once per instance, which allows to quickly sample multiple solutions per instance. We note that not all models use static embeddings. Some approaches update all instance embeddings after each action (c.g., Zhang et al. (2020)), which allows the embeddings to contain information the current solution state 8t.
3

---

Published as a conference paper at ICLR 2022
Ix per instance
Ix per solution
Decoder
Decodet
Bacodet
Instiance
Emnhodding
02
Actian
stmpplig
soutpling
Figure 1: Sampling solution for the TSP with model po(m]() that uses static instance embeddings.
3.1 EMBEDDING UPDATES
Our first proposed strategy, called EAS-Emb, updates the embeddings generated by encoder using a loss function consisting of an RL component L RLL and an imitation learning (IL) component Lu. The loss LRL is based on REINFORCE (Williams 1992) and is the expected cost of the generated solutions, [C[((T) We aim to adjust the embedding parameters to increase the likelihood of generating solutions with lower costs (e.g., shorter tour length for the TSP). The loss L is the negation of the log- log-probability of (re-) (re-)generating the best solution seen so far. We adjust the embedding parameters increase this probability.
More formally, for an instance we generate the embeddings w using a given encoder. Based on w, we can (repeatedly) sample solution и whose cost is C(T).. A subset of the embeddings @ C w is adjusted to minimize LRL using the gradient
VoCRI(a) Ex [(C(TT) - ).) lo [a]]
where qo ( ()) II ga(at W), and b. is baseline (we use the baseline proposed in Kwon et al. (2020) for our experiments).
For the second loss Lu., let न be the best solution found far for the instance that consists of the actions .j...., är. We use teacher forcing to make the decoder (o(-)s during which obtain the probability values associated with the actions a...... @r. We increase the log-likelihood of generating से by adjusting á using the gradient
st, () generate the solution म.
T
VaLiL(W) V log qo ()) V log II (o,ls,))
The gradient of the overall loss CRI is defined as (aLRII()) where À is tunable parameter. If high value for À is selected, the search focuses on generating solutions that are similar to the incumbent solution. This accelerates the convergence of the search policy, which useful when the number of search iterations limited.
VoLri( (
(n.
We note that both decoding processes required for RL and IL can be carried out in parallel, using the same forward pass through the network. Furthermore, only the parameters are instance specific, while all other model parameters are identical for all instances. This makes parallelization of multiple instances in a batch more efficient both in time and memory.
3.2 ADDED-LAYER UPDATES
We next propose EAS-Lay, which adds an instance-specific residual layer to a trained model. During the search, the weights in the added layer updated, while the weights of all other original layers are held fixed. We use both RL and IL, similarly to EAS- Tmb-Emb in Section 3.I
We formalize EAS-Lay as follows. For each instance I insert layer
I. (h) = h + ((ReLu(hW) + b+) + b2)
(3)
into the given decoder qs. resulting in a slightly modified model T where &e = (W', W 22,62).
The layer takes in the input h and applies two linear transformations with ReLu activation function in between. The weight matrices a and W and the bias vectors 5' and 6² are adjusted throughout the search via gradient descent. The weights in the matrix W and the vector 1² are initialized to
4

---

Published as a conference paper at ICLR 2022
zero that the added layer does not affect the output of the model during the first iteration of the search. The gradient for LR is given as
VVLRi(V) = F [[C(T=) ba) V log as (T)]
with (T) = =IT== Io.0 (ot w)) and b. is baseline. The gradient for Ctt. is defined similarly.
Note that the majority of the network operations are not instance specific. They can be applied identically to all instances running in parallel as a batch, resulting in significantly lower runtime during search. The position at which the new layer is inserted has an impact on the performance of EAS-Lay, and identifying the best position usually requires testing. In general, the memory requirement of this approach can be reduced by inserting the additional layer closer towards the output layer of the network. This decreases the number of layers to be considered during backpropagation. We noticed for wransformer-base architectures that applying the residual layer L-(-) to the query vector q before is passed to the single attention head usually results a good performance.
3.3 TABULAR UPDATES
EAS-Emb and EAS-Lay require significantly less memory per instance than the original active search. However, they still need to store many gradient weights associated with multiple layers for the purpose of backpropagation. This significantly limits the number of solutions one can generate in parallel. We hence propose EAS-Tab, which does not require backpropagation, but instead uses simple lookup table to modify the policy of the given model. For each action at a given state, the table provides guide on how to change its probability, so that the sampled solution has higher chance at being similar to the best solution found in the past.
Formally, at each step during the sequential generation of solution, we redefine the probability of selecting action a in the state 8t as qo (a (t) w) Qg(ar.a)) and renormalize over all possible actions using the softmax function. Here, is hyperparameter, and g is function that maps each possible state and action pair to an entry in the table Q. The network parameters remain unchanged, resulting in fast and memory efficient solution generation. The hyperparameter a is similar to the temperature value proposed in [Bello et al.] (2016) and modifies the steepness of the probability distribution returned by the model (lower values increase the exploration of the search). During search, the table Q is updated with the objective of increasing the quality of the generated solutions. More precisely, after each iteration, Q is updated based on the best solution found so far consisting of the actions uI...., äT at states $i,..., S7, respectively, with
max (o() ) if g(), E (g(āa, Aaa. 3T)}
(5)
otherwise
The hyperparameter a defines the degree of exploitation of the search. If a higher value of a is used,
the probabilities for actions that generate the incumbent solution are increased.
In contrast to embedding or added-layer updates, this EAS method requires deeper understanding of the addressed combinatorial optimization problem to design the function g(s,, For example, for the TSP with n nodes we use a table Q of size n X in which each entry Qi, corresponds to a directed edge e.,j of the problem instance. The probability increases for the same directed edge that was used in the incumbent solution. This definition of g( az) effectively ignores the information on all the previous visits stored in state st. focusing instead on the current location (city) in choosing the next move. We note that this EAS approach is similar to the ant colony optimization algorithm (Dorigo) et al. 2006), which has been applied wide variety of combinatorial optimization problems.
4 EXPERIMENTS
We evaluate all EAS strategies using existing, state-of-the-art RL based methods for three different combinatorial optimization problems. For the first two, the TSP and the CVRP, we implement EAS for the POMO approach (Kwon et al. 2020). For the third problem, the JSSP, we use the L2D method from Zhang al. (2020). We extend the code made available by the authors of POMO (MIT license) and L2D (no license) with our EAS strategies to ensure a fair evaluation. Note that we only make minor modifications these methods, and we the models trained by the authors when available.
5

---

Published as a conference paper at ICLR 2022
We run all experiments core of an Intel Xcon 4114 CPU at 2.2 GHz for each experiment. Our source code available at https:/ githuh..hh... com/ ang EAS We use the Adam optimizer (Kingma & Ba 2014) for all EAS approaches. The hyperparameters X, a, o, and the learning rate for the optimizer are tuned via Bayesian optimization using scikit-optimize (Head et al., (020) on separate validation instances, which are sampled from the same distribution as the test instances. The hyperparameters are not adjusted for larger instances used to evaluate the generalization performance.
GPU cluster using single Nvidia Tesla V100 GPU and single
4.1 TSP
The TSP is well-known routing problem involving finding the shortest tour between set of n. nodes (i.... cities) that visits each node exactly once and returns to the starting node. We assume that the distance matrix obeys the triangle incquality.
Implementation POMO uses a model that is very similar to the AM model from Kool et al. (2019).
The model generates instance embeddings only once per instance and does not update them during construction. The probability distribution over all actions are generated by a decoder, whose last layer is single-headed attention layer. This last layer calculates the compatibility of a query vector to the key vector k; for each node i. In this operation, the key vector k; is an embedding that has been computed separately, but identically for each input (i.e., node i) during the instance encoding process. For EAS-Emb, we only update the set of single-head keys k, (i = .....,.., n). For EAS-Lay we apply the residual layer (-) described in Equation t the query vector q before it passed to the single attention head. For EAS-Tab, we use table Q of size n x n and the mapping function directed edge ct,j of the problem instance.
g(s,, 0z) such that each entry Qi.y corespondents
Setup We use the 10,000 TSP instances with 100 from Kool et al. (2019) for testing and three additional sets of 1,000 instances to evaluate generalization performance. We evaluate the EAS approaches against just using POMO with greedy action selection, random sampling, and active search as in Bello et al. (2016). In all cases, we use the model trained on instances with n = 100 made available by the POMO authors. For greedy action selection, POMO generates 8 n solutions for an instance of size n (using 8 augmentations and n different starting cities). In all other cases, we generate 200 n solutions per instance (over the course of 200 iterations for the (E)AS approaches). The batch size (the number of instances solved parallel) is selected for each method individually to fully utilize the available GPU memory. We compare the exact solver Concorde (Applegate et al.) 2006). the heuristic solver LKH3 (Helsgaun, 2017). the graph convolutional neural network with beam search (GCN-BS) from Joshi et al. (2019). , the 2-Opt based deep learning (2-Opt-DL) approach from de O. da Costa et al. (2020), the learning improvement heuristics (LIH) method from Wu et al.) (2021), the conditional variational autoencoder (CVAB-Opt) approach (Hottung et al. 2021). and deep policy dynamic programming (DPDP) (Kool et al. (2021).
Results Table [ shows the average costs, average gap and the total runtime (wall-clock time) for each instance set. The exact solver Concorde performs best overall, as it is highly specialized TSP
Table 1: Results for the TSP
Testing (10k inst.)
Generalization (1k instances)
100
125 Gap
150
200
Method
Obj.
Gap
Time
Obj.
Time Obj.
Gap
Time
Obj.
Gap
Time
Concorde
7.765
0.000%
82M
8,583
0.000%
12M 9.346 0.000% 17M 10.687
0.000%
31
LKH3
7.765
0.000%
8H
8.583
0.000%
73M 9,346
0.000%
99M
10.687 0.000%
3H
GCN-BS
7.87
1.39%
40M
2-Opt-DL
7.83
0.87%
41M
LIH
7.87
1.42%
2H
CVAF-On Opt
0.343%
6D 8.646
0.736%
21H
9.482
1.454%
30H
DPDP
7.765
0.004% %
2H 8,589 0.070%
31M
9.434
0.942%
44M
11.154
4.370%
74M
Greedy
7.776 0.146%
IM 8.607
0.278%
<1M
9,397
0.542%
<IM
10.843
1.457%
IM
Sampling
7.770
0.074%
4H 8.595
0.145%
45M
9.378
0.334%
78M
10.838
1.416%
3H
OMO
Active S.
7.768
0.046%
SD 8.591
0.095%
15H
9.364
0.192%
1911
10.735
0.447%
2411
EAS-Emb
7.769 0.063%
SH 8.591
0.092%
57M
9.363 0.174%
2H 10.730
0.400% %
4H
EAS-Lay
0.053% 7.769
7H 8.591 0.089%
74M
9.363 0.176%
2H 10.737
0.471%
4H
EAS-Tab
(77668 0.048%
SH 8.591
0.091%
49M
9.365 0.196%
IH 10.756
0.650%
3H

---

Published as a conference paper at ICLR 2022
solver. Of the POMO-bases -ased approaches, the original active search offers the best gap to optimality, but requires 5 days of rumtime. EAS significantly lowers the runtime while the gap is only marginally larger. DPDP performs best among ML-based approaches. However, DPDP relies and problem-specific beam search, whereas EAS methods are completely problem-independen.. On the larger instances, EAS significantly improves generalization performance, reducing the gap over sampling by up to 3.6x. We also evaluate active search using the imitation learning loss, but observe no impact on the search performance (see Appendix [
handcrafted
4.2 CVRP
The goal of the CVRP is to find the shortest routes for a set of vehicles with limited capacity that must deliver goods set of customers. We again the POMO approach basis for our EAS strategies. As is standard in the ML literature, we evaluate all approaches on instance sets where the locations and demands are sampled uniformly at random. Additionally, we consider the more realistic instance sets proposed in Hottung & Tierney (2020) with up to 297 customers (see Appendix A
Implementation We use the same EAS implementation for the CVRP as for the TSP.
Setup We use the 10,000 CVRP instances from Kool et al. (019)) for testing and additional sets of 1,000 instances to evaluate the generalization performance. Again, we compare the EAS approaches to POMO using greedy action selection, sampling and active search. We generate the same number of solutions per instance as for the TSP. We compare to LIH, CAVE-Opt, DPDP, NeuRewriter (Chen)
& Tian 2019) and neural large neighborhood search (NLNS) from Hottung & Tiemnyy (2020).
Results Tablee]]sone the average costs, the average gap to LKH3 and the total wall-clock time for all instance sets. EAS-Lay outperforms all other approaches on the test instances, including approaches that rely on groblem-speccffe knowledge, with a gap that beats LKH3. Both other EAS methods also find solutions of better quality than LKH3, which is quite an accomplishment given the many years of work on the LKH3 approach. We note it is difficult to provide a fair comparison between single-core, CPU-bound technique like LKH3 and our approaches that assuming a linear speedup, at least 18 CPU cores would be needed for LKH3 to match the runtime of EAS-Tab. On the generalization instance sets with n 125 and 150, the EAS approaches also outperform LKH3 and CVAE-Opt while being significantly faster than active search. On the instances with n 200, active search finds the best solutions of all POMO based approaches with gap of 0.22% to LKH3, albeit with a long runtime of 36 hours. We hypothesize that significant changes to the learned policy are necessary to generate high-quality solutions for instances that are very different to those seen during training. Active search's 's ability to modify all model parameters makes it easier to make those changes. EAS-Tab offers the worst performance on the instances with n = 200 with gap of 11.8% This is because EAS-Tab is very sensitive to the selection of the hyperparameter a, meaning that EAS-Tab requires hyperparameter tuning on some problems to generalize more effectively. Adjusting for the 200 case improves EAS-Tab's 's gap to least 3.54%, making it slightly better than greedy or sampling.
GPU. Nonetheless,
Table 2: Results for the CVRP on instances with uniformly sampled locations and demands
Testing (10k inst.)
Generalization (1k instances)
Yt
100
Y1 = 125
71
150
= 200
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Obj. Gap
Time
LKH3
15.665
0.00%
6D]17.50
0.00%
19H
19.22
0.00% 20H
22.00
0.00%
25H
NLNS
15.99
2.23%
62M
18.07
3.23%
9M 19.96
3.86%
12M
23.02
4.66%
24M
NeuRewriter
16.10
66M
LIH
16.03
2.47%
5H
CVAE-Opt
1.36%
11D
17.87
2.08%
36H
19.84
3.24%
46H
DPDP
15.63
-0.13%
23H
17.51
0.07%
3H
19.31
0.48%
22.26 5H
1.20%
9H
Greedy
15.76
0.76%
2M
1.29%
<1M
19.64
2.18%
1M 22.90
4.12%
1M
OMO
Sampling
15.67
0.17%
7H 17.60
0.54%
73M
19.48
1.35%
2H 23.18
5.35%
5H
Active S.
15.63
-0.07%
8D 17.47
-0.21%
25H
19.21
-0.03%
2911
22,05
0.22%
3611
EAS-Emb
15.63
-0.08%
9H 17.47
-0.21%
93M
19.22
0.03%
3H 22.19
0.88%
6H
EAS-Lay
15.61
-0.23%
17.46 -0.24%
2H
19.21
-0.04%
3H 22.10
0.45%
8H
EAS-Tab
15.62
-0.14%
8H
81117.50
0.00%
80M
19.36
0.72%
211
24.56
11.8%
5H
7

---

Published as a conference paper at ICLR 2022
4.3 JSSP
The JSSP is a scheduling problem involving assigning jobs to a set of heterogencous machines. Each job consists of multiple operations that are run sequentially on the set of machines. The objective is to minimize the time needed to complete all jobs, called the makespan. We evaluate EAS using the L2D approach, which is
ML based construction method using a graph neural network.
Implementation L2D represents JSSP instances as disjunctive graphs in which each operation of an instance is represented by node in the graph. To create a schedule, L.2D sequentially selects the operation that should he scheduled next. To this end, an embedding h2 is created for each node in a step-wiss encoding process. In contrast POMO, the embeddings h2 are recomputed after each decision step t. Since EAS-Emb requires static embeddings, we modify the network to use h = h² + A as an embedding for node at step t, where h is vector that is initialized with all weights being set to zero. During the search with EAS-Emb we only adjust the static component hST of the embedding with gradient descent. For EAS-Lay. we insert the residual layer L (-)-) described in Equation to each embedding h1 separately and identically. Finally, for EAS- Tab, we use table Q of size 10 x 10], where |O| is the number of operations, and we design the function g(8t, (z) so that the entry Q corresponds to selecting the operation 0j directly after the operation Oç.
Setup We use three instance sets with 100 instances from Zhang et al. (2200) for testing and to evaluate the generalization performance. We use the exact solver Google OR- Tools (Perron Furnon) compare
baseline, allowing it maximum runtime of 1 hour per instance. Furthermore, to L2D with greedy action selection. Note that the performance of the L2D implementation is CPU bound and does not allow different instances be batch processed. We hence solve instances sequentially and generate significantly fewer solutions per instance than for the TSP and the CVRP. For sampling, active search and the EAS approaches sample 8,000 solutions per problem instance over the course of 200 iterations for the (efficient) active search approaches.
Results Table 3 shows the average gap the OR-Tools solution and the total wall-clock time per instance set. EAS-Emb offers the best performance for all three instance sets. On the 10 10 instances, EAS-Emb reduces the gap by 50% in comparison to pure sampling. Even on the 20 15 instances reduces the gap to 16.8% from 20.8% for pure sampling, despite the low number of sampled solutions per instance. EAS-Lay offers performance that is comparable to active search. We note that if I.21) were to more heavily use the GPU, instances could be solved in batches, thus drastically reducing the runtime of EAS-Lay and EAS-Tab. While EAS-Ta Tab shows similar performance to active search on the test instance set, it is unable to generalize effectively to the larger instances.
4.4 SEARCH TRAJECTORY ANALYSIS
To get a better understanding of how efficient active search improves performance, we monitor the quality of the solutions sampled each of the 200 iterations of the search. Figure 2 reports the average quality over all test instances for the JSSP and over the first 1,000 test instances for the TSP and CVRP. As expected, the quality of solutions generated via pure sampling does not change over the course of the search for all three problems. For all other methods, the quality of the generated solutions improves throughout the search. Thus, all active search variants successfully modify the (model) parameters in way that increases the likelihood of generating high-qualit solutions.
Table 3: Results for the JSSP
Testing (100 inst.)
Generalization
(100 instances)
10 x 10
15
15
20 x
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
OR-Tools
807.6
0.0%
37S]
1188.0
0.0%
3H
1345.5 0.0%
80H
Greedy
988.6
22.3%
20S
1528.3
28.6%
44S 1738.0
29.2%
60S
Sampling
871.7
8.0%
8H 1378.3
16.0%
25H 1624.6
20.8%
40H
Active S.
854.2
5.8%
811 1345.2
13.2%
32H1 1576.5
17.2%
50H
EAS-Emi
837.0
3.7%
7H 1326.4
11.7%
22H 1570.8
16.8%
37H
EAS-Lay
859.6
6.5%
7H 1352.6
13.8%
25H 1581.8 17.6%
46H
EAS-Tab Tab
860.2
6.5%
811 1376.8
15.9%
2911
1623.4
20.7%
51H
8

---

Published as a conference paper at ICLR 2022
TSP
CVRP
2057
1.764
1.00-
33.75
Seepling
1.00
$2.70
1042 Lae
1.00
AS
13.05
1.700
20
11G
233
20.0
Poneatios
Figure 2: Average costs of sampled solutions at each iteration (best viewed in color).
CVRPP
3S5P
6:0H
RAS-
3.00
RRSS-ay
1630
1960
Figure 3: Influence of À on the solution quality for EAS- and EAS-Lay.
For the TSP, EAS-Emi and EAS-Lay offer nearly identical performance, with EAS-Tar outperforming both by a very slight margin. The original active search significantly more unstable, which likely the result of the learning rate being too high. Note that the learning rate has been tuned on an independent validation set. These results indicate that selecting a suitable learning rate is significantly more difficult for the original active search than for our efficient active search variants where only subset of (model) parameters are changed. For the CVRP, all EAS variants find better solutions on average than the original search after only few iterations. Keeping most parameters fixed seems to simplify the underlying learning problem and allows for faster convergence. For the JSSP, EAS-Emi offers significantly better performance than all other methods. The reason for this is that the I.21) approach uses only two node features and has a complex node embedding generation procedure. While the original active search must fine tune the entire embedding generation process modily the generated solutions, EAS-Emb can just modify the node embedding directly.
4.5 ABLATION STUDY: IMITATION LEARNING LOSS
We evaluate the impact of the imitation learning loss Lu. of EAS-Emb and EAS-Lay with a sensitivity and ablation analysis for the hyperparameter A. We solve the first 500 test instances (to reduce the computational costs) for the TSP and CVRP, and all test instances for the JSSP using EAS-Emb and EAs-Lay with different À values. The learning rate remains fixed to a value determined in independent tuming runs in which À is fixed to zero. Figure 3 shows the results for all three problems. For the TSP and the CVRP, the results show that L.r. can significantly improve performance. When is set to 0 or very small values, Lu. is disabled, thus including Lu is clearly beneficial the TSP and CVRP. For the JSSP, the inclusion of Li does not greatly improve performance, but it does not hurt it, either. Naturally, À should not be selected too low or too high as either too little or too much intensification can hurt search performance.
CONCLUSION
We presented a simple technique that can be used to extend ML-based construction heuristics by an extensive search. Our proposed modification of active search fine tunes a small subset of (model) parameters single instance at test time. We evaluate three example implementations of EAS that all result in significantly improved model performance in both testing and generalization experiments on three different, difficult combinatorial optimization problems. Our approach of course comes with some key limitations. Search requires time, thus for applications needing extremely fast (or practically instant) solutions, greedy construction remains a better option. Furthermore, while the problems experiment have the same computational complexity as real-world optimization problems, additional work may be needed to handle complex side constraints as often seen in industrial problems.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The computational experiments in this work have been performed using the Bielefeld GPU Cluster.
REFERENCES
David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver, 2006.
Irwan Bello, Hieu Pham, Quoc Le, Mohammad Norouzi, and Samy Bengio. Neural Combinatorial Optimization with Reinforcement Learning. ArXiv, abs/1611.00 610,, 2016.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, pp. 6278-6289, 2019.
Paulo R de O. da Costa, Jason Rhuggenaath, Yinggian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, pp. 465-480. PMLR, 2020.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the TSP by policy gradient. In International Conference the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 170-181. Springer,
2018.
Marco Dorigo, Mauro Birattari, and Thomas Stutzle. Ant colony optimization. IEEE computational intelligence magazine, 1(4):28-39 2006.
Jonas K Falkner and Lars Schmidt-Thieme. Learning solve vehicle routing problems with time windows through joint attention. arXiv preprint arXiv:2006.09100 2020.
Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large TSP instances. arXiv preprint arXiv:2012.10658, 2020.
Tim Head, Manoj Kumar, Holger Nahrstaedt, Gilles Louppe, and Iaroslav Shcherbatyi. scikit- optimizelscikiloopiiiize September 2020. URL /ttg:://dol.or//11...22222 [0044755]
Keld Helsgaun. An extension of the Hin--eemighan-Helggann TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
John J. Hopfield. Neural Networks and Physical Systems with Emergent Collective Computational Abilities. Proceedings of the National Academy of Sciences of the United States of America, 79(8): 2554-2555 2558, 1982. ISSN 00278424.
André Hottung and Kevin Tierney Neural large neighborhood search for the capacitated vehicle routing problem. In European Conference on Artificial Intelligence, pp. 443-450, 2020.
André Hottung, Shunji Tanaka, and Kevin Tiemeey Deep learning assisted heuristic tree search for the container pre-marshalling problem. Computers & Operations Research, 1 113:10478,, 2020.
André Hottung, Bhanu Bhandari, and Kevin Tierney. Learning a latent search space for routing problems using variational autoencoders. In International Conference Learning Representations, 2021.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.0122: 2019.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In I. Guyon, U. V. Luxburg, Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 42280090, 2014.
10

---

Published as a conference paper at ICLR 2022
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic program- ming for vehicle routing problems. aaXiiv preprint arX1v:2102.11750 2021.
Yeong-Das Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: policy optimization with multiple optima for reinforcement learning. In H. Larochelle, M. Ranzato, Hadsell, M. Balcan, and H. Lin (eds.), Advances Neural Information Process- ing Systems, volume 33, pp. 21188-2118 Curran Associates, Inc., 2020.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9839 9849, 2018.
Bo Peng. Jiahai Wang, and Zizhen Zhang. A deep reinforcement learning algorithm using dy- namic attention model for vehicle routing problems. International Symposium on Intelligence Computation and Applications, pp. 636-650 Springer, 2019.
Laurent Perron and Vincent Furnon. OR-Tools. URL https::/ //dee opers. com/
opt imiiiaiiiiin////
Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi. Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845 858, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Natalia Vesselinova, Rebecca Steinert, Daniel F. Perez-Ramirez, and Magnus Boman. Learning combinatorial optimization on graphs: A survey with applications to networking. IEEE Access, 120388-12041 16, 2020.
Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, and Christian Prins. A unified solution framework for aulti-atrribte vehicle routing problems. European Journal of Operational Research, (34(3):658-673 2014.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015.
Ronald J Williams. Simple statistical gralient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4):229-255 256, 1992.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Transactions on Industrial Informatics, 1 17(7)486114871 2021.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pp. 1621-1633 2020.
11

---

Published as a conference paper at ICLR 2022
A EXPERIMENTS FOR MORE REALISTIC CVRP INSTANCES
We provide results from additional experiments for the CVRP on more realistic instances show that our approach is effective at solving instances with a wide range of structures. Our EAS methods are implemented in the same way as in Section 4.2
Setup We evaluate EAS on 9 instance sets from Hottung & Tierney (2020) (consisting of 20 instances each) that have been generated based on the instances from Uchoa et al. (2017) performing runs per instance. The characteristics of the instances vary significantly between sets, but all instances in the same set have been sampled from an identical distribution. For each instance set we train a new model for 3 weeks a separate, corresponding training set. For testing, we run all (efficient) active search approaches for 200 iterations using the newly trained models. Additionally, we test the generalization performance by solving all instance sets with EAS-Lay using the CVRP model of Section 442 that has been trained on the uniform instances (with n = 100) from Kool et al. (2019) and call this Lay*. We only evaluate the generalization performance of EAS-Lay (the best performing EAS approach from Section (.2) to keep the computational costs low. In all experiments, we use hyperparameters tuned for the uniform CVRP instances. We compare NLNS, LKH3 and the state-of-the-ar unified hybrid genetic search (GS) from Vidal et al. (0014). As is standard in the operations research literature, we round the distances between customers to the nearest integer. Furthermore, we solve instances sequentially and not in batches of different instances. However, to make better use of the available GPU memory, we solve up to 10 copies of the same instance in parallel for the EAS approaches and for POMO with sampling. The best solution found so far is shared between all runs, which has an impact on the imitation learning loss Lu for EAS- Emb and EAS-Lay. For EAS-Tab we set Q = (1- 9) Q + 3 Qalab, where Q9tob is the lookup table for the best solution over all runs and B is linearly increased from 0 to over the course of the search.
Results Table 4 shows the gap to the unified hybrid genetic search and the average runtime per instance for all methods. For EAS- and additionally the generalization performance when using the model trained on uniform CVRP instances (with better solution than NLNS and LKH3 on 8 out of the 9 instance sets. EAS-Tab outperforms NLNS and LKH3 on all but two instance sets. As side note, we have found that the original active search (AS) performs surprisingly well, outperforming LKH3 on 3 instance sets, even though it still cannot surpass our newly proposed EAS methods. The version of EAS-Lay (marked with a star) that uses the model trained on uniform instances with n = 100 performs surprisingly well with gaps between 0.26% to 4. 4.08% to the GS.
report the performance of the instance set specific models
100). The later results marked with star. EAS-Emb and EAS-Lay both find
Table 4: Results for the CVRP on the instance sets from Hottung & Tiemny 2020
Gap GS in POMO-EAS Tab
Avg, Runtime minutes POMO-EAS
POMO
POMO Sam. AS
Inst.
Sam. AS
Emb Lay Lay*
NLNS LKH
Emb Lay
Tab NLNS LKH GS Lay*
XE
100
0.86
0.65
0.23 0.26
0.61 0.31
0.32
2.12
0.9
1.3
1.3
1.4
1.5
0.9
3.2
6.2
0.6
XE
128
0.76 0.80
0.26
0.25
0.29
0.44
0.54
1.3
1.6
1.8
2.0
2.1
1.4
3.2
2.0
1.2
XE 5
180
0.51 0.20
0.09
0.09
0.54 0.13
0.58
0.16
2.5
2.2
3.3
3.7
3.8
2.7
3.2
1.1
1.4
XE_7
199
1.50 0.88
0.37 0.45
1.29 0.80
2.03
0.72
3.3
2.4
4.2
4.7
4.9
3.5
3.2
3.6
2.4
XE
213
1.96 1.30
0.64
0.71
4.08 0.83
2.26
1.09
3.7
2.5
4.6
5.2
5.4
3.9
10.2
1.1
2.4
XE 236
1.42
1.22
0.82 0.84
1.76
0.94
0.65
0.78
2.7
5.2
5.1
5.6
4.8
10.2
1.1
3.2
XE_
269
1.40 0.88
0.38 0.56
2.83
0.80
0.82
1.55
7.1 3.5
8.7
6.6
7.1
7.6
10.2
5.7
3.6
XE_ 279
1.81
2.17
0.85 0.96
1.27
1.81
1.32
7.3
3.3
8.8
6.6
7.2
7.9
10.3
5.8
5.5
XB_17 297
1.66
0.97
0.44
0.65
2.15
0.92
1.41
1.23
8.9
3.8
8.8
6.8
7.1
9.4
10.3
2.5 4.2
B ABLATION STUDY: ACTIVE SEARCH LOSS
We evaluate if applying the imitation learning loss component used by EAS-Emb and EAS-Lay to the original active search can significantly improve the performance. To this end, we solve all test instances using active search with and without the imitation learning loss component. Note that the hyperparameters for each approach have been tuned independently instances. shows the results. We observe no significant impact of the imitation learning loss Lu, on the performance of active search. This means that active search with imitation learning loss is
separate validation set
12

---

Published as a conference paper at ICLR 2022
Table 5: Performance of active search with and without imitation learning loss component.
TSP (10k inst.)
CVRP (10k inst.)
JSSP (100 inst.)
Active search loss
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
RL RL
7.768 0.046%
SD 15.634 -0.070%
8D 854.20 20 5.80%
8H 9H
7.769 0.052%
5D
15.634 -0.073%
8D 854.16 5.78%
TSP
CVRP
Auragg te qemelnyy (80
Averge pap 3M00 (53
Aveaae op to Oi Dock (K)
4-
0.0-
1000
Figure 4: Influence of a on the solution quality for EAS-Tab
not competitive with EAs-Lay and EAS-Emb across all problems, even when sharing the same loss function.
C PARAMETER SWEEP: EAS-TAB INTENSIFICATION
We investigate the impact of the hyperparameter exploitation the search. By setting a to zero (or very small values) we essentially disable the lookup table, thus examining its impact on the search. We again solve all three problems with different values of on a subset of test instances. We fix a independently based on tuning on a separate of validation instances. Figure provides the results for adjusting For all three problems, = 10 provides the best trade-off between exploration and exploitation. Note that low a values (which reduce the impact the lookup table updates) hurt performance, meaning that the table based adjustments are effective in all cases.
EAS-Tab, which controls the degree of
13


Reviews:
[{"review_id": "rvE19tJlsZM", "reviewer": "Reviewer_JA4x", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents an interesting idea that seems to have a large impact. The\nevaluation is thorough and fair, the results are convincing. This is a good\npaper that should be accepted.\n\nThere are a few minor points that were unclear to me and might warrant further\ndiscussion. The results for the TSP in Table 1 show that concorde is often the\nfastest solver. This is somewhat counter-intuitive, especially compared to LKH,\nas it is a complete solver. The proposed method is also often much slower. Some\nexplanation of this would be helpful for the reader to understand what exactly\nis going on there.\n\nThe most nebulous part of the proposed method to me is the placement of the new\nlayer, which sounds like it might be quite difficult in practice and potentially\nrequire expensive evaluation of different alternatives. A more in-depth\ndiscussion of how the authors determined this for their experiments, along with\nsome recommendations on how to do this in a new setting, would make the paper\nstronger and more applicable in practice.\n", "summary_of_the_paper": "The paper proposes a new method of updating deep neural networks for\ncombinatorial optimization problems during search using reinforcement learning.\nIn particular, the authors show that by updating only part of the network,\nbetter results can be achieved at lower cost. They describe and evaluate their\nmethod on different combinatorial optimization problems, comparing to other\nmachine-learning-based approaches as well as \"traditional\" solvers.", "summary_of_the_review": "Interesting method with promising results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Q3ari2Coevn", "reviewer": "Reviewer_cAC5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n1. The paper is clear, well organised and well written \n1. The presented approach seems applicable to any constructive method as long as it has a encoder/decoder type of architecture \n1. 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. \n1. 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 \n1.Nice discussion in Sec 4.4. to explain possible reasons of why one of the proposed variants work best for each problem. \n\n**Weaknesses**\n1. 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.\n1. 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)\n1. 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?\n\n\n**Recommendation**\n\nI 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.\n\n**Questions**\n1. What is the motivation of adding a new layer to fine-tune (EAS-Lay) versus fine-tuning some existing layers of the model?\n1. 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.\n1. 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. \n1. 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?\n1. 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?\n\n\n**Additional feedback**\n* In Introduction\n    *  “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?\n    * “..wide adaption” —> adoption\n* Sec 3.Background: the decoder is introduced with parameter $\\omega$, but this one is only defined as the embeddings in the next paragraph \n* 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.\n* Figure 2: y-axis is the average costs. Optimality gap would be more relevant (and consistent) especially if instances have different sizes\n* \n\n\n", "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.\n", "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.\n\n\n### Update after rebuttal\n\nI thank the authors for precisely answering all my questions and concerns.\nI am happy to confirm my initial recommendation of accepting the paper.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Bg6vejkaHuA", "reviewer": "Reviewer_xF8a", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nNovelty: 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.\n\nPresentation: 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.\n\nThere are some ambiguities in the paper:\n\n1. 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.\n\n2. 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:\n(a) EAS uses less memory, and hence we can solve more instances in parallel, or\n(b) EAS is computationally more efficient, i.e., it uses less CPU-time to achieve the competitive performance, or\n(c) a combination of the above?\nIt 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.\n\nMinor comments:\nIn figure 3, the x-axis should be labeled lambda.\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "80s1qc9w8MQ", "reviewer": "Reviewer_4SkE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- This paper studies an exciting area—machine learning for combinatorial optimization—where machine learning has the potential to make a big impact.\n- 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.\n- 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.\n\nWeaknesses:\n- 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$. \n- 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.\n\nDetailed comments:\n- Page 2: I’m not sure that “exemplary” is the right word here; I would remove it.\n- 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)