Year: 2021

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.

heading: 1 INTRODUCTION
text: In recent years, a wide variety of machine learning (ML) based methods for combinatorial optimization problems have been proposed. While early approaches failed to outperform traditional operations research methods, the gap between handcrafted and learned heuristics has been steadily closing. However, the main potential of ML-based methods lies not only in their ability to 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 construction methods and improvement methods. Improvement methods search the space of complete solutions by iteratively refining a given start solution. They allow for a guided exploration of the search space and are able to find high-quality solutions. However, they usually rely on problemspecific components. In contrast, construction methods create a solution sequentially starting from an empty solution (i.e., they consider a 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-specific 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.e., the underlying distribution from which solutions are sampled is never changed throughout the search.
Bello et al. (2016) propose a generic search strategy called active search that allows an 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 a 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 to 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, we show that for some problems, EAS finds even better solutions than the original active search. All EAS implementations can be easily applied to existing ML 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 (JSSP). 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-art ML based approaches, and even the well-known 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.

heading: 2 LITERATURE REVIEW
text: 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 Vinyals et al. (2015) efficiently learns the conditional probability of a permutation of a given input sequence, e.g., a permutation of cities for a TSP solution. The authors solve TSP instances with up to 50 cities via supervised learning. Bello et al. (2016) report that training a pointer network via actor-critic RL instead results in a better performance on TSP instances with 50 and 100 cities. Furthermore, graph neural networks are used to solve the TSP, e.g., a graph embedding network in Khalil et al. (2017) and a 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 Kool et al. (2019). Nazari et al. (2018) propose a model with an attention mechanism and a recurrent neural network (RNN) decoder that can be trained via actor-critic RL. Kool et al. (2019) propose an attention model that uses an encoder that is similar to the encoder used in the transformer architecture Vaswani et al. (2017). Peng et al. (2019) and Xin et al. (2021) extend the attention model to update the node embeddings throughout the search, resulting in improved performance at the cost of longer runtimes for the CVRP. Falkner & Schmidt-Thieme (2020) propose an attention-based model that constructs tours in parallel for the CVRP with time windows.
While ML-based 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 a graph neural network based approach for the job shop scheduling problem (JSSP). Li et al. (2018) use a 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, we refer to Vesselinova et al. (2020).
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 a graph convolutional network to create a heat-map and a beam search to search for solutions. Similarly, Fu et al. (2020) use a graph convolutional residual network with Monte Carlo tree search to solve large TSP instances. Kool et al. (2021) use the model from Joshi et al. (2019) 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). Chen & Tian (2019) propose an approach that iteratively changes a local part of the solution. At each iteration, the trainable region picking policy selects a part of the solution that should be changed and a trainable rule picking policy selects an action from a given set of possible modification operations. Hottung & Tierney (2020) propose a method for the CVRP that iteratively destroys parts of a 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 an improving solution from a specified local neighborhood (e.g., the 2-Opt neighborhood) to solve routing problems. Hottung et al. (2021) learn a continuous representation of discrete routing problem solutions using conditional variational autoencoders and search for solutions using a generic, continuous optimizer.

heading: 3 SOLVING COMBINATORIAL OPTIMIZATION PROBLEMS WITH EAS
text: We propose three EAS implementations that adjust a small subset of (model) parameters in an iterative search process. Given an 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-specific 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 are 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-quality solution for an instance is found, the adjusted parameters are discarded, so that the search process can be repeated on other instances. All strategies efficiently generate solutions to a 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 a neural network based model pθ(π|l) with weights θ that can be used to generate a solution π given an instance l. State-ofthe-art approaches usually use a model that consists of an encoder and a decoder unit. The encoder usually creates static embeddings ω that describe the instance l using a computationally expensive encoding process (e.g., Kool et al. (2019); Kwon et al. (2020)). The static embeddings are then used to autoregessively construct solutions using the decoder over T time steps. At each step t, the decoder qφ(a|st, ω), with weights φ ⊂ θ, outputs a probability value for each possible action a in the state st (e.g., for the TSP, each action corresponds to visiting a different city next). The starting state s1 describes the problem instance l (e.g., the positions of the cities for the TSP and the starting city) and the state st+1 is obtained by applying the action at selected at time step t to the state st. The (partial) solution πt is defined by the sequence of selected actions a1, a2, . . . , at. Once a complete solution, πT , fulfilling all constraints of the problem is constructed, the objective function value C(π, l) of the solution can be computed (e.g., the tour length for the TSP).
Figure 1 shows the solution generation for a TSP instance with a model that uses static embeddings. The static embeddings ω 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 qφ(a|st, ω). 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 (e.g., Zhang et al. (2020)), which allows the embeddings to contain information on the current solution state st.

heading: 3.1 EMBEDDING UPDATES
text: Our first proposed strategy, called EAS-Emb, updates the embeddings ω generated by an encoder using a loss function consisting of an RL component LRL and an imitation learning (IL) component LIL. The loss LRL is based on REINFORCE (Williams, 1992) and is the expected cost of the generated solutions, E [ C(π) ] . We aim to adjust the embedding parameters to increase the likelihood of generating solutions with lower costs (e.g., a shorter tour length for the TSP). The loss LIL is
the negation of the log-probability of (re-)generating the best solution seen so far. We adjust the embedding parameters to increase this probability.
More formally, for an instance l we generate the embeddings ω using a given encoder. Based on ω, we can (repeatedly) sample a solution π whose cost is C(π). A subset of the embeddings ω̂ ⊆ ω is adjusted to minimize LRL using the gradient
∇ω̂LRL(ω̂) = Eπ [ (C(π)− b◦)∇ω̂ log qφ(π | ω̂) ] (1)
where qφ(π | ω̂) ≡ ∏T t=1 qφ(at | st, ω̂), and b◦ is a baseline (we use the baseline proposed in Kwon et al. (2020) for our experiments).
For the second loss LIL, let π̄ be the best solution found so far for the instance l, that consists of the actions ā1, . . . , āT . We use teacher forcing to make the decoder qφ(·|st, ω̂) generate the solution π̄, during which we obtain the probability values associated with the actions ā1, . . . , āT . We increase the log-likelihood of generating π̄ by adjusting ω̂ using the gradient
∇ω̂LIL(ω̂) = −∇ω̂ log qφ(π̄ | ω̂) ≡ −∇ω̂ log T∏ t=1 qφ(āt|st, ω̂). (2)
The gradient of the overall loss LRIL is defined as ∇ω̂LRIL(ω̂) = ∇ω̂LRL(ω̂) + λ · ∇ω̂LIL(ω̂), where λ is a tunable parameter. If a 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 is useful when the number of search iterations is limited.
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.

heading: 3.2 ADDED-LAYER UPDATES
text: 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 are updated, while the weights of all other original layers are held fixed. We use both RL and IL, similarly to EAS-Emb in Section 3.1.
We formalize EAS-Lay as follows. For each instance l we insert a layer
L?(h) = h+ ((ReLu(hW 1 + b1)W 2 + b2) (3)
into the given decoder qφ, resulting in a slightly modified model q̃φ,ψ , where ψ = {W 1, b1,W 2, b2}. The layer takes in the input h and applies two linear transformations with a ReLu activation function in between. The weight matrices W 1 and W 2 and the bias vectors b1 and b2 are adjusted throughout the search via gradient descent. The weights in the matrix W 2 and the vector b2 are initialized to zero so that the added layer does not affect the output of the model during the first iteration of the search. The gradient for LRL is given as
∇ψLRL(ψ) = Eπ [ (C(π)− b◦)∇ψ log q̃φ,ψ(π) ] , (4)
with q̃φ,ψ(π) ≡ ∏T t=1 q̃φ,ψ(at | st, ω), and b◦ is a baseline. The gradient for LIL 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 transformer-based architectures that applying the residual layer L?(·) to the query vector q before it is passed to the single attention head usually results in a good performance.

heading: 3.3 TABULAR UPDATES
text: 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 a simple lookup table to modify the policy of the given model. For each action at a given state, the table provides a guide on how to change its probability, so that the sampled solution has a higher chance at being similar to the best solution found in the past.
Formally, at each step t during the sequential generation of a solution, we redefine the probability of selecting action at in the state st as qφ(a|st, ω)α · Qg(st,at) and renormalize over all possible actions using the softmax function. Here, α is a hyperparameter, and g is a 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 α 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 ā1, . . . , āT at states s̄1, . . . , s̄T , respectively, with
Qg(st,at) = { max(1, σqφ(a|st,ω)α ), if g(st, at) ∈ {g(ā1, s̄1), . . . , g(āT , s̄T )} 1, otherwise
(5)
The hyperparameter σ defines the degree of exploitation of the search. If a higher value of σ 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(st, at). For example, for the TSP with n nodes we use a tableQ of size n×n in which each entryQi,j corresponds to a directed edge ei,j of the problem instance. The probability increases for the same directed edge that was used in the incumbent solution. This definition of g(st, at) 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 to a wide variety of combinatorial optimization problems.

heading: 4 EXPERIMENTS
text: 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 et 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 to these methods, and we use the models trained by the authors when available.
We run all experiments on a GPU cluster using a single Nvidia Tesla V100 GPU and a single core of an Intel Xeon 4114 CPU at 2.2 GHz for each experiment1. We use the Adam optimizer (Kingma & Ba, 2014) for all EAS approaches. The hyperparameters λ, σ, α, and the learning rate for the optimizer are tuned via Bayesian optimization using scikit-optimize (Head et al., 2020) 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.
1Our implementation of EAS for POMO will be made available after publication under the MIT license.

heading: 4.1 TSP
text: The TSP is a well-known routing problem involving finding the shortest tour between a set of n nodes (i.e., cities) that visits each node exactly once and returns to the starting node. We assume that the distance matrix obeys the triangle inequality. The TSP has received significant attention from the ML community and is a well established benchmark for ML-based optimization approaches.
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 a single-headed attention layer. This last layer calculates the compatibility of a query vector q to the key vector ki for each node i. In this operation, the key vector ki 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 ki (i = 1, . . . , n). For EAS-Lay we apply the residual layer L?(·) described in Equation 3 to the query vector q before it is passed to the single attention head. For EAS-Tab, we use a table Q of size n× n and the mapping function g(st, at) such that each entry Qi,j corespondents to a directed edge ei,j of the problem instance.
Setup We use the 10,000 TSP instances with n = 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 · 8 ·n solutions per instance (over the course of 200 iterations for the (E)AS approaches). The batch size (the number of instances solved in parallel) is selected for each method individually to fully utilize the available GPU memory. We compare to 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 (CVAE-Opt) approach (Hottung et al., 2021), and deep policy dynamic programming (DPDP) (Kool et al., 2021).
Results Table 1 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 a highly specialized TSP solver. Of the POMO-based approaches, the original active search offers the best gap to optimality, but requires 5 days of runtime. EAS significantly lowers the runtime while the gap is only marginally larger. DPDP performs best among ML-based approaches. However, DPDP relies on a handcrafted and problem-specific beam search, whereas EAS methods are completely problem-independent. 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 B).

heading: 4.2 CVRP
text: The goal of the CVRP is to find the shortest routes for a set of vehicles with limited capacity that must deliver goods to a set of n customers. We again use the POMO approach as a 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 in our supplemental material (Appendix A). EAS-Emb and EAS-Lay outperform LKH3 on 8 of those 9 instance sets (and EAS-Tab on 7 out of 9).
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. (2019) 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 & Tierney (2020).
Results Table 2 shows 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 problem-specific 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 a single-core, CPU-bound technique like LKH3 and our approaches that use a GPU. Nonetheless, 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 n = 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 a 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 ability to modify all model parameters makes it easier to make those changes. We note, however, that our EAS approach can be easily expanded to include more adjustable parameters as needed. EAS-Tab offers the worst performance on the instances with n = 200 with a gap of 11.8%. This is because EAS-Tab is very sensitive to the selection of the hyperparameter α, meaning that EAS-Tab requires hyperparameter tuning on some problems to generalize more effectively. Adjusting α for the n = 200 case improves EAS-Tab’s gap to at least 3.54%, making it slightly better than greedy or sampling.

heading: 4.3 JSSP
text: The JSSP is a scheduling problem involving assigning jobs to a set of heterogeneous 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 a state-of-the-art 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 a node in the graph. To create a schedule, L2D sequentially selects the operation that should be scheduled next. To this end, an embedding hv is created for each node v in a step-wise encoding process. In contrast to POMO, the embeddings hv are recomputed after each decision step t. Since EAS-Emb requires static embeddings, we modify the network to use h̃tv = h t v +h ST v as an embedding for node v at step t, where h ST v is a vector that is initialized with all weights being set to zero. During the search with EAS-Emb we only adjust the static component hSTv of the embedding with gradient descent. For EAS-Lay, we insert the residual layer L?(·) described in Equation 3 to each embedding hv separately and identically. Finally, for EAS-Tab, we use a table Q of size |O| × |O|, where |O| is the number of operations, and we design the function g(st, at) so that the entry Qi,j corresponds to selecting the operation oj directly after the operation oi.
Setup We use three instance sets with 100 instances from Zhang et al. (2020) for testing and to evaluate the generalization performance. We use the exact solver Google OR-Tools (Perron & Furnon) as a baseline, allowing it a maximum runtime of 1 hour per instance. Furthermore, we compare to L2D with greedy action selection. Note that the performance of the L2D implementation is CPU bound and does not allow different instances to 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 we 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 to 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 it 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 L2D 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-Tab shows similar performance to active search on the test instance set, it is unable to generalize effectively to the larger instances.

heading: 4.4 SEARCH TRAJECTORY ANALYSIS
text: To get a better understanding of how efficient active search improves performance, we monitor the quality of the solutions sampled at 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 a way that increases the likelihood of generating high-quality solutions.
For the TSP, EAS-Emb and EAS-Lay offer nearly identical performance, with EAS-Tab outperforming both by a very slight margin. The original active search is significantly more unstable, which is 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 a subset of (model) parameters are changed. For the CVRP, all EAS variants find better solutions on average than the original search after only a few iterations. Keeping most parameters fixed seems to simplify the underlying learning problem and allows for faster convergence. This explains why the EAS strategies outperform the original active search with respect to solution quality and runtime on the CVRP. For the JSSP, EAS-Emb offers significantly better performance than all other methods. The reason for this is that the L2D 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 to meaningfully modify the generated solutions, EAS-Emb can just modify the node embedding directly.

heading: 4.5 ABLATION STUDY: IMITATION LEARNING LOSS
text: We evaluate the impact of the imitation learning loss LIL of EAS-Emb and EAS-Lay with a sensitivity and ablation analysis for the hyperparameter λ. 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 tuning 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 LIL can significantly improve performance. When λ is set to 0 or very small values, LIL is disabled, thus including LIL is clearly beneficial on the TSP and CVRP. For the JSSP, the inclusion of LIL 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.

heading: 5 CONCLUSION
text: 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 to a 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 we experiment on 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. For future work, we intend to investigate these sorts of constraints and to what extent existing RL methods must be adjusted to effectively solve these types of problems.

heading: A EXPERIMENTS FOR MORE REALISTIC CVRP INSTANCES
text: We provide results from additional experiments for the CVRP on more realistic instances to 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 3 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 on a separate, corresponding training set. For testing, we run all (efficient) active search approaches for 200 iterations using the hyperparameters tuned for the uniform benchmark instances (with n = 100). We compare to NLNS, LKH3 and the state-of-the-art unified hybrid genetic search (UHGS) from Vidal et al. (2014). 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 LIL for EAS-Emb and EAS-Lay. For EAS-Tab we set Q̃ = (1− β) ·Q+ β ·Qglob, where Qglob is the lookup table for the best solution over all runs and β is linearly increased from 0 to 1 over the course of the search.
Results Table 4 shows the gap to UHGS and the average runtime per instance for all methods. EAS-Emb and EAS-Lay both find 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 a 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.

heading: B ABLATION STUDY: ACTIVE SEARCH LOSS
text: 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 on separate validation set instances. Table 5 shows the results. We can observe no significant impact of the imitation learning loss LIL on the performance of active search. This means that active search with imitation learning loss is not competitive with EAS-Lay and EAS-Emb across all problems, even when sharing the same loss function.

heading: C PARAMETER SWEEP: EAS-TAB INTENSIFICATION
text: We investigate the impact of the hyperparameter σ on EAS-Tab, which controls the degree of exploitation of the search. By setting σ 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 α independently based on tuning on a separate set of validation instances. Figure 4 provides the results for adjusting σ. For all three problems, σ = 10 provides the best trade-off between exploration and exploitation. Note that low σ values (which reduce the impact of the lookup table updates) hurt performance, meaning that the table based adjustments are effective in all cases.

Review summaries:
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. 

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.

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.

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.