Learning a Latent Search Space for Routing Problems using Variational Autoencoders
Authors: André Hottung
Bhanu Bhandari
Kevin Tierney
Venue: ICLR 2021 Poster (2021)
Keywords: heuristic search
variational autoencoders
learning to optimize
routing problems
traveling salesperson problem
vehicle routing problem
combinatorial optimization

Abstract: Methods for automatically learning to solve routing problems are rapidly improving in performance. While most of these methods excel at generating solutions quickly, they are unable to effectively utilize longer run times because they lack a sophisticated search component. We present a learning-based optimization approach that allows a guided search in the distribution of high-quality solutions for a problem instance. More precisely, our method uses a conditional variational autoencoder that learns to map points in a continuous (latent) search space to high-quality, instance-specific routing problem solutions. The learned space can then be searched by any unconstrained continuous optimization method. We show that even using a standard differential evolution search strategy our approach is able to outperform existing purely machine learning based approaches. 

Published as a conference paper at ICLR 2021
LEARNING A LATENT SEARCH SPACE FOR ROUTING PROBLEMS USING VARIATIONAL AUTOENCODERS
André Hottung
Bhanu Bhandari
Bielefeld University
University of Massachusetts Amherst
Bielefeld, Germany
Amherst, MA, USA
andre. hht.:unggun--bbeeeeflll.l.
bhanučhandar@ccs umass edu
Kevin Tierney
Bielefeld University
Bielefeld, Germany
kevin. www.eiennnnnnnn-eeeeeellllleeeee
ABSTRACT
Methods for automatically learning to solve routing problems are rapidly improv- ing performance. While most of these methods excel at generating solutions quickly, they are unable effectively utilize longer run times because they lack a sophisticated search component. We present a learning- -baee optimization ap- proach that allows guided search in the distribution of high-quality solutions for a problem instance. More precisely, our method uses a conditional variational autoencoder that learns map points in continuous (latent) search space to high- quality, instance-specifee routing problem solutions, The learned space can then be searched by any unconstrained continuous optimization method. We show that even using a standard differential evolution search strategy our approach is able to outperform existing purely machine learning based approaches.
INTRODUCTION
Significant progress has been made in learning to solve optimization problems via machine learning (MI.) Especially for practical applications, learning-based approaches are of great interest because of the high labor costs associated with the development of completely hand-crafted solution ap- proaches. For routing problems such as the traveling salesperson problem (TSP) and the capacitated vehicle routing problem (CVRP), recent ML-based approaches are able to generate good solutions for small problem instances in a fraction of a second (e.g., Kool et al.] (2019)) However, in many real-world applications of these problems users gladly accept more computation time for solutions of even higher quality. Recently proposed approaches (e.g., [ottung & Tierney (2020)) address this demand and integrate learning-based components with high-level search procedures. While these approaches offer improved performance over non-search-ber based methods, they rely on domain knowledge encapsulated in the high-level search procedures.
In this work, we present a learning- based optimization approach for routing problems that is able to perform an extensive search for high-quality solutions. contrast to other approaches, our method does not rely on Nomain-speciff high-level search procedures. Our approach learns an instance- specific mapping of solutions isting continuous optimization method. We use a conditional variational autoencoder (CVAF) that learns to encode a solution given instance as a numerical vector and vice versa. Some genetic algorithm variants (e.g.. Gonçalves & Resende (2012) use numerical vectors to represent solutions to combinatorial optimization problems. However, these approaches rely on decoding schemes that carefully handcrafted by domain experts. In contrast, approach learns the
continuous search space that can then be searched via any ex-
decoding schema on its own, requiring no domain or optimization knowledge on the side of the user.
The performance of optimization algorithm heavily depends on the structure of the fitness land- scape of the search space, such as its smoothness. solutions close to each other in the search space semantically similar, resulting in a smooth landscape, the employed search algorithm can

---

Published as a conference paper at ICLR 2021
iteratively move towards the more promising areas of the search space. It has been observed for some problems that variational autoencoders (VAEs) are capable of learning a latent space in which semantically similar inputs are placed in the same region. This allows, for example, semantically meaningful interpolation between two points in the latent space (see e.g. [Berthelot et al. (2018) ) However, it is unclear if this property upholds for a conditional latent space that encodes routing problems. We show experimentally that our CVAE-based approach is indeed capable of learning a latent search space in which neighboring solutions have a similar objective function value. Further- more, we introduce a novel technique that addresses the issue of symmetries in the latent space and show that it enables our method to match and surpass tfat-oof-the-ar ML-based methods. We train our method using high-quality solutions because we aim to learn latent search space that contains mostly high-quality solutions. Hence, our method usually requires a long offline phase (e-g.. to gen- erate solutions using slow, domain-independent generic solver). However, this offline phase is offset by fast, online solution generation.
We focus the TSP and the CVRP, which are two of the most well-researched problems in the optimization literature. The TSP is concerned with finding the shortest tour between a set of cities that visits each city exactly once and returns to the starting city. The CVRP describes routing problem where the routes for multiple vehicles to a set of customers must be planned. All customers have a certain demand of goods and all vehicles have maximum capacity that they can carry. All routes must start and end at the depot. The task is to find a set of routes with minimal cost so that the demand of all customers is fulfilled and each customer is visited by exactly one vehicle. We consider the versions of the TSP and CVRP where the distance matrix obeys the triangle inequality.
The contributions of this work are as follows:
We propose a novel approach that learns a continuous, latent search space for routing prob- lems based on CVAEs.
We show that our approach is able to learn a well-struetured latent search space.
We show that the learned search space enables standard differential evolution search strategy to outperform state-of-the-ane ML methods
2 RELATED WORK
In Hopfield & Tank (185), was first proposed to use an ML-based method to solve a routing problem. The authors use a Hopfield network to solve small TSP instances with up to 30 cities. In Vinyals et al. (2015). pointer networks are proposed and trained to solve TSP instances with up to 50 cities using supervised learning. [Bello et al.] (2166) extend this idea and train pointer network via actor-critic reinforcement learning. More recently, graph neural networks have been used to solve the TSP, e.g., graph embedding network in Khalil et al. (2017). a graph attention network in Deudon et al. (2018), or a graph convolutional network in Joshi et al. (2019). The significantly more complex CVRP has first been addressed in Nazari et al. (2018) and Kool et al. (2019), in which a recurrent neural network decoder coupled with an attention mechanism and a graph attention network are used, respectively. While some of these methods use a high-level search procedure (such as beam search), all of them are focused on finding solutions quickly (in under one second). In contrast, our approach is able to exploit longer runtime (more than one minute for larger instances) to find solutions of better quality.
A couple of approaches use local search like algorithms combined with ML techniques to solve routing problems. Chen & Tian (2019) propose to learn an improvement operator that makes small changes to an existing solution. The operator is applied to solution iteratively to find a high- quality solutions for the CVRP. However, with a reported runtime of under half a second for the CVRP with 100 nodes, the method not focused on performing an extensive search.
Hottung & Tierney (2020). another iterative improvement method for the CVRP is proposed that integrates learned hcuristics into a large neighborhood search framework. The method is used to perform an extensive search with reported runtimes of over one minute for larger instances. In contrast to method, the high-level large neighborhood search framework contains domain specific components and is known perform exceptionally well on routing problems (Ropke & Pisinger 2006).
Perhaps most similar to our work is the line of research based on in which the authors use VAE to learn a continuous latent search space for discovering molecules.
et al. (2018),
2

---

Published as a conference paper at ICLR 2021
Instanio
Instance
Uncoustrained
Encoder
Docoder
Coutimouu Optiniier
Instance Solution
Solution
Solution Costs
Solution
@a) Training
(b) Search
Figure 1: CVAE-Opt overview
They use additional Gaussian process model that is trained to predict the the quality of molecules given their latent search space representation to allow for gradient-based search. Kusner et al. (2017) and Jin et al. (2018) use similar setup, but use Bayesian optimization for the search. Winter et al. (2019) propose to use particle swarm optimization to search a learned latent space for new molecules. To more limited degree, the idea of optimizing in a continuous learned space has also been used for neural architecture optimization (Luo et al., 2018). In contrast to the aforementioned methods, we do not use separate model to predict the solution quality based their latent repre- sentation, because decoding and evaluating solutions in our setting is cheap (compared to molecules or neural network architectures). Furthermore, our approach addresses fundamentally different problem, because routing problems must be solved with respect to given context (i.e., a problem instance that describes location coordinates that must be visited) and we hence use CVAE this work. Learning latent space conditioned on problem instance (with the number of possible in- stances being basically infinite) is significantly more challenging. [chter et al. (2018) propose to use CAVES to learn latent space conditioned on problem instances to represent solutions to robot motion planing problems. However, they only sample solutions at random from the learned distri- bution and do not perform a guided search. We show that the learned structured latent space of our approach enables a guided search that significantly outperforms random sampling.
Different generative models have been used to sample
population members in probabilistic evolutionary algorithms known as estimation of distribution algorithms (e.g., a Helmholtz machine (Zhang & Shin 2000), restricted Boltzmann machine (Tang al. 2010, [him al., 2010 Probst et al. 2017). or a VAF (Garciarena et al,) 2018 [Bhattacharjee & Gras) (019)). ). All these methods are focused on how explore existing search space using generative models. In contrast, our method is focused on learning the search space itself, leaving the actual search to a generic optimizer.
3 METHOD
Our novel approach, called CVAE-Opt, learns a continuous (latent) search space for routing prob- lems that can be searched by any continuous optimization method. It is based CVAE that learns to map solutions to routing problem instances to a continuous, n--dimensional space. In contrast to conventional search spaces, the learned latent search is trained to contain only high-quality solutions.
Autoencoders are neural networks that are used to learn an efficient encoding of data. They consist of encoder and decoder network. The encoder learns to reduce input dimensional space and the decoder tries to reconstruct the input x based on 2. The objective of the training to minimize the difference between the input æ and the output of the decoder, requiring the network to learn an efficient encoding of x. In contrast, VAES are generative models that do use a deterministic encoder. but instead an encoder that parameterizes an approximate posterior distribution over 2. In our context, we do not want to train the decoder to generate solutions for only a single instance (e.g., a given set of coordinates for the TSP), but instead for instances of certain instance type (e.g., all TSP instances with 50 cities). We thus use CVAE (Sohn et al., 2015), which enables us to learn latent search space conditioned on the problem instances.
point in low
3.1
VARIATIONAL AUTOENCODER-BH BASED COMBINATORIAL OPTIMIZATION
The overall training process of CVAE-Opt is shown in Figure la The stochastic encoder q[2[1, s) receives problem instance and high-quality solution s and outputs an n--imensiioal vector 2. The decoder p(s|1, 2) is given together with the instance / and outputs solution s'. One objective
3

---

Published as a conference paper at ICLR 2021
of the training is to minimize the difference between the original high-quality solution and the solution s' generated by the decoder. While the decoder is powerful enough to construct a good solution based the instance alone, it is also given the latent variable that describes the aspects of the solution s that the decoder cannot reliably infer on its own. The second objective during training is ensure that high-quality solutions can be generated for values of the latent variable that have not been seen during training. This objective is explained in more detail below.
Figure lb shows the iterative search process, in which the decoder p(s((, 2) is used together with any unconstrained continuous optimizer to search for solutions to a problem instance 1. The uncon- strained continuous optimizer navigates the search through the learned latent search space. At each iteration, the optimizer outputs a vector 2 describing point in the latent search space. The decoder generates a solution s' based on 2 and the objective function value of s' is returned to the optimizer. With an effective optimizer and the learned search space, high-quality solutions to can be found.
Routing problem representation We describe a routing problem instance by a graph G = (V, E), with V {vo, .... ) The representation of a problem instance I consists of set of feature vectors æ0: Ti,,..., En. where v; describes node U;. For the TSP, each node represents a location (e.g., a city) with each two-dimensional feature vector describing the location's coordinates. For the CVRP, the node Uo represents the depot, and all other nodes represent the customers. As in Nazari et al. (2018), each feature vector is dimensinnsi and describes the unfulfilled demand of a location, the remaining capacity of the vehicle, and the coordinates of the location. For both problems, a solution s describes a sequence of locations :s.....;; Usr (for the TSP, T n) in which the first location is the starting city (for the TSP) or the depot (for the CVRP). We note that formalism focuses on routing problems on a Euclidean plane. While we anticipate that our approach will work for other types of combinatorial optimization problems (with adjustment of the input layers), we save showing this for future work.
3.2 MODEL
We implement the encoder (2)2,,, and the decoder pa(s)(, using neural networks, with 6 and 0 denoting the network weights. earlier work, (e.g.,NNzza) et al. (2018)) routing problems are often modeled as Markov decision processes where a solution is constructed by sequence of actions (i.e., which node should be visited next). We follow that approach and train our decoder pp (s|1, 2) to select the location that should be added to the solution at each step / E (1....,7), TY, with the first element of the solution being predefined (TSP: the starting city, CVRP: the depot). As Nazari ett al. (2018), we use masking schema to prevent the model from selecting actions that would result in an unfcasible solution. The probability of the decoder of generating a solution s can be decomposed as (Sutskever al. 2014):
2)( = II pls.lss.....,.
Like the decoder, the encoder generates the latent variable for solution so...., ST to a problem instance sequentially. At step E {T, it encodes the t-th element of the solution.
Similar to Nazari al. (2018), allow the input representation to change during encoding and decoding. The input Tg.t: In,t at time step can be changed to reflect the new sub-problem defined by the problem instance and the constraints introduced by the partially constructed solution 80. 8t-1- In the following, we omit the index when referring to the input data of the model to allow for better readability. For the CVRP, we update the demands of the customers and the remaining vehicle capacity based on the decisions of the model in earlier decoding steps. For the TSP, we make no changes to the problem instance representation.
Network architecture The architecture of the encoder and the decoder is shown in Figure 2 Both use a linear embedding layer and an attention mechanism to encode/decode solutions sequentially. Weights are shared between identical components in the encoder and decoder. This allows not only for faster training, but also enforces a shared view of the encoder and decoder on the given problem representation. A more detailed description of the network architecture is given in Appendix A.
4

---

Published as a conference paper at ICLR 2021
Lin
softmax
8g
211
Pir
Pir
Lin
6
A4
4A
44
AAA
RNN
Atb
Att
RNN:
h
RNNN
ho
h1
112
Embedding
Enbosdiing
h
11
hg
400
(a) Encoder
(b) Decoder
Figure 2: CVAE-Opt model
3.3 TRAINING
The objective of the model training is two-fold. The first objective is maximize the llog)Jikelihood of reconstructing a solution to an instance I encoded by the encoder (= via the decoder (o(s) (s|,, [1, =). The second objective is to keep the posterior distribution of the encoder close to given desired probability distribution p(z). We use a standard Gaussian distribution (μ = 0, 1) for p(z) and measure the difference between both distributions with the Kullback-Leile (KL) divergence. As in 3-VAEs (Higgins et al. 2017), we weight the objectives during training using the parameter 8:
C(o. 0. s. s. = (=)(s Poo
Dxu
(2)
Symmetry breaking Optimization problems are commonly subject to symmetrical solutions, which are multiple solutions that represent the same semantic solution, but differ in terms of their syntax. For example, for the TSP the solution sequence .n....,88 represents the same solution as the solution sequence $1...., Sn, Sg. For the CVRP, the subtours can be ordered in any order the solution sequence without changing the underlying solution. This might lead to the CVAE placing identical solutions in different regions of the learned latent search space because they are represented by different solution sequences. To force the model to learn a representation of the underlying solution and not the solution sequence. solution to the input, rather than the exact same solution as the input. The symmetrical solutions used during training are chosen at random for each epoch.
train the model to reproduce symmetrical
EXPERIMENTS
We evaluate CVAE-Opt datasets of TSP and CVRP instances and compare it to state-of-the-a optimization approaches. We use two different unconstrained continuous optimizers in our experi- ments: basic differential evolution (DE) algorithm (Storn & Price 1997) and random search (RS). In the following, we refer to the two variants of CVAE-Opt as CVAE-Opt-DE and UVAE-Opt-RS. In all experiments, CVAE-Opt is run single Nvidia Tesla V100 GPU and single core of a Intel Xeon 41 14 CPU at 2.2 G We evaluate CVAE-Opt on TSP and CVRP instances with 20, 50, and 100 nodes. For each of these six problem classes, we generate instances with identical properties to the instances used in Kool et al. 2019)) using the instance generator made available by the authors. We use 93,440 instances for model training, 100 for search validation, and 1,000 for testing the search problem class.
4.1 SETUP
Training For the TSP, we solve all instances to optimality using CONCORDE (Applegate et al.
2006). For the CVRP, create high-quality solutions using the heuristic solver LKH3 (Helsgaun, 2017 We run LKH3 a single time for each instance with the hyperparameter configuration used in
Helsgaun (017).. We train separate models for each instance class for 300 epochs. Every 25 epochs
OOr implementation of CVAF-Opt available
twwb. https///gg..ta..ccc//oootttt////

---

Published as a conference paper at ICLR 2021
the model is evaluated by using its decoder in a CVAE-Opl search setting to look for solutions to the 100 validation instances. The search setup (i.e., the hyperparameter configuration) is identical to the one used in the later testing/deployment stage. The model offering the best validation performance is used to search for solutions to the test instances.
The ideal selection of the hyperparameter 3 depends the problem class and the search setup. For each problem class we repeat the training process a small number (<20) of times and pick the model with the best validation search performance. All other search hyperparameters are identical over all training runs and have not been tuned. The training batch size is set to 128 and the Adam optimizer (Kingma & Ba 2014) with a learning rate of 10-3 is used.
Search The DE algorithm employed in CVAE-Opt-De maintains a population of vectors in the learned latent search space that is improved by crossover and mutation. Offspriin vectors are created by combining three vectors of the population using vector arithmetic, as described in [Storn & Price (1997). We slightly modify the employed DE algorithm to better profit from the parallel computing capabilities of a GPU: Instead of generating one offspring solution at time, we decode and evaluate a batch of solutions per iteration.
In all experiments of CVAE-Opt-DE, DE algorithm, 600 offspring vectors are generated and decoded in one batch. The initial population vectors are sampled uniformly random from the bounded search space. To determine the bounds, we encode 1,000 separate model validation instances (with the encoder) to points in the latent space. The bounds are then selected that 99% of the coordinates of the points are within the bounds. This ensures that the search operates in regions of the latent search space known by the decoder even if the posterior distribution of the encoder differs substantially from the standard Gaussian distribution. The crossover probability CR and the differential weight F of the DE are set to 0.95 and 0.3, respectively. Solutions are generated greedily by the decoder (i.e., the action with the highest probability value is selected at each step). The search terminates after 300 iterations. We note that we do not tune these hyperparameters and that the reported results can thus likely be improved.
DE population size of 600. At each iteration of the
In CVAE-Opt-RS, the latent variables are sampled randomly from Gaussian distribution. We also evaluated sampling from a uniform distribution using the same bounds as for CVAE-Opt-DE, but observed that this slightly deteriorates the performance. All other components of CVAE-Opt-RS (and its hyperparameters) are identical to CVAE-Opt-DE.
4.2 SYMMETRY BREAKING
First, we evaluate the effectiveness of our symmetry breaking mechanism. We train five models with symmetry breaking and five models without symmetry breaking for the TSP and the CVRP with 50 and 100 nodes each. In all training runs is set le-3. Figure 3 shows the search performance of the models after the final training epoch on the validation instances (in terms of the gap to the solutions obtained via CONCORDE and LKH3). In all cases our symmetry breaking mechanism leads to an significant performance improvement. For the TSP instances the mean gap is reduced from 0.09% to 0.04% for instances with 50 nodes, and from 1.23% to 0.37% for instances with 100 nodes. Similarly, for the CVRP symmetry breaking reduces the mean gap from 3.18% to 0.33% and 5.66% to 1.67% for instances with 50 and 100 nodes, respectively.
4.3 INFLUENCE OF
To evaluate the influence of the parameter 3, we repeat the training with different 3 values (again five times per value and problem setting). We only consider TSP and CVRP instances with 100 nodes because the experiments are computationally expensive. Figure 4 shows the performance (gap to CONCORDE and LKH3) of the models after the final training epoch when searching for solutions to the validation instances. We observe that in our setting the best search performance can be observed for 3 values of le-2 and 1e-3 for the TSP and the CVRP, respectively. This is a significant deviation from the proposed /3 values (> 1) in Higgins et al. (0017). A high 3 value corresponds to strong limit on the capacity of the latent information channel. We hypothesize that our extensive search procedure benefits from latent (search) space that is able represent many instances.

---

Published as a conference paper at ICLR 2021
TSP
CVRP
TSP100
CVRPI10
1.5
Cop (8)
Clip (K)
Gay (80
10-
Chap (56)
2.0
0.0
75
TSP
CIVÓPicO
1-3
16-2
Figure 3: Symmetry breaking
Figure 4: Influence of B
med dit in bibo fonnel whiton
dit to bet found solatonn
3.0
TSP100
CVRP100
3.0
S01 35 30 45 00 65 10
45
2.0
2.0-
0.0
Radiddan
0.2
2.0
50m.
Rooiiduee
0.1
0.2
0.5
5.0
30
Figure 5: Solution quality vs. distance in the latent search space
Figure 6: Learned latent search space for the TSP along 2 of 100 dimensions
4.4 STRUCTURE OF THE LEARNED SEARCH SPACE
The performance of any search algorithm depends on the structure of the search space. Ideally, so- lutions of similar quality should be placed in similar regions of the search space. We conduct the following experiment evaluate if our method learns a (latent) search space in which solutions of high quality can on average be found in the proximity of other high-quality solutions: First, we sam- ple 1,000 solutions for a routing problem instance from the learned search space. The best of these solutions functions as reference solution. Next, we sample solutions from multiple hyperspheres around the reference solutions, only considering points within the defined bounds of the search space. For each hypersphere we sample 100 solutions, and discard all solutions that are identical to the reference solutions. We repeat this experiment for each the 1,000 test instances per problem class. Figure 3 shows the absolute cost difference of the sampled solutions the reference solution for the TSP and CVRP with 100 nodes (see Appendix [ for all results). The results show for all problem classes that, on average, solutions close to the high-quality solutions also of similar quality (in contrast to solutions farther away), indicating that the search space is well structured.
This experiment also shows that our method successfully learns search space mostly containing high-quality solutions. Even randomly selected solutions that have a euclidean distance of five from the high-quality reference solution only have an average absolute cost difference of 1.13 for the TSP and 1.51 for the CVRP (both with 100 nodes). As an illustrative example, Figure 6 shows of learned latent search space for randomly selected TSP instance with 20 nodes (the search space is only shown along 2 of 100 dimensions). While this visualization is not artificially selected, it does not allow for any generalizable assertions.
4.5
COMPARATIVE EXPERIMENTS
TSP For comparison the state-of-the-art, compare CVAE-OPt-DE and CVAE-OpI-RS to the AM approach from Kool et al. (2019). We run the AM approach on the same machine as CVAE- Opt using the code and the models made available by the authors, sampling 500,000 solutions for each instance. Figure 7 shows the performance for all three methods over the course of the search process (with 95% confidence interval). For instances with 20 nodes all methods achieve a very low (< 0.1) average gap to optimality, albeit the AM method performs slightly worse than the CVae-based approaches. Instances with 50 and 100 nodes are computationally harder and allow CVAE-Opt-DE to take advantage of its guided search in the learned latent search space. For both instance groups, CVAE-Opt- seconds of the search. This is the case although CVAE- Oet---tt--eEE needs significantly more time per sampled solution than the other approaches. Table shows the final results after the completion of the search and additionally compares the performance of CVAE-Opt to Concorde, LKH3 and the
outperforms the AM approach and CVAE -EE-Opt-RR after the first few

---

Published as a conference paper at ICLR 2021
Average top to optimaliy (3)
TS120
TSP50
TSP100
9.5-
0.1--
Aperage gop optinalit
0.-
VAE-0y4-D8
VAR-Oye Oye RS
Aveeage 10p oplimalll
20-
VAB-0g-08
VAR
1G-
0.22
0.5-
0.0
10
20
90
00
Praniime (s)
Runtime
[
Rundinee
Figure 7: TSP search performance (gap to optimality)
CVR1200
CVRP50
CVRP100
AM
AM
VAB Dya
10.8-
295
KAB--0y
Average Cbats
Upe-11
Anerage Cost
VAR--0p--0
0.00-
16.2-
Averagen
00.65
16.0-
8.15-
00.5
6.40
15.0
Runtime (X)
Runtine
Runtins (9)
Figure 8: CVRP search performance (absolute costs)
graph convolutional network approach using beam search and the shortest- tour heuristic (GCN-BS) from Doshí et al. (2019). We note that GCN-BS, in contrast other evaluated learning- based meth- ods, solves instances in batches (of size 200) making a direct comparison of the runtime difficult.
CVRP First, we compare CVAE-Opt-DE and CVAE-Opt-RS to the AM approach using the same hyperparameters for the TSP instances. Figure g shows the performance of all three methods. Note that we report the absolute cost instead of the gap to optimality because it is not currently computationally feasible to solve CVRP instances CVAE-Opt-DE outperforms both other methods given similar runtime. We note that the significant performance difference between CVAE-Opt-RS and OyAt-OOt-DE is the most unbiased confirma- tion that our approach is able to learn well-structured search space. If the learned search would have no meaningful structure, we would expect both approaches to have similar performance.
optimality. For all three instance sizes
Table Tsoows additional results comparing both CVAE Opt implementations to LKH3, NLNS (Hot- tung& Tiemey 2020), and NeuRewriter (Chen & Tian 2019). We run all approaches except for NeuRewriter on the same machine as CVAE-Opt. For NLNS, we use 10 cores and limit the runtime to the time needed by CVAF-Opt-DE. For NeuRewriter, we report the results obtained by the authors (we thus mark the results with a star) on instances with identical properties. CVAE-Opt- Opt-D- DE finds better solutions than NeuRewriter on all instance sizes (due to its much longer runtime) and comes close to the performance of LKH3 and NLNS (which profit from expert designed high-level search components that CVAE-Opt does not require) on instances with 20 and 50 customers.
4.6 GENERALIZATION
We evaluate the generalization performance of CVAE-OpI-DE and the AM approach by using model trained on instances with 100 nodes to solve instances with 95, 105, 125 and 150 nodes. We
Table 1: Comparison to existing approaches TSP and CVRP instances
CVRP
Avg. Gap
Runtime
Avg. Cost
Runtime
Method
n=20
n=50
n=100
n=20
n=50
n=100
n=20
n=50
n=100
n=20
n=
n= n=100
CVAE-OpI-DE
0.00%
0.02%
0.34%
10.5
21.5
55.
6.14
10.40
15.75
20.8
41.0
94.7
CVAE-Opt-RS
0.00%
0.20%
1.35%
6.3
16.8
50.5
6.15
10.54
16.11
16.6
38.2
92.5
AM
0.02%
0.25%
1.65%
4.3
21.7
6.21
10.52
15.93
97.2
GCN-BS
0.00%
0.02%
1.25%
0.1
0.2
0.3
NeuRewriter*
6.16
10.51
16.10
0.1
0.2
0.4
NINS
6.14
10.36
15.54
22.7
40.8
93.3
Concorde
0.00%
0.00%
0.00%
0.1
0.5
LKH3
0.00%
0.00%
0.00%
0.1
2.8
6.14
10.36
15.54
29.0
53.8
8

---

Published as a conference paper at ICLR 2021
Table Generalization ability of models trained on instances with 100 nodes
TSP
CVRP
Avg.
Gap
Runtime AM
Avg. Gap
LKH3
Runtine
CVAE-Opt
AM
VAE-Opt
Cone.
CVAE-Opt
AM
CVAE-Opt
AM
LKH3
95
0.31%
160%
55.9
73.8
0.4
1.27%
2.37%
92.6
83.8
52.0
100
0.34%
1.65%
55.1
82.1
1.36%
2.46%
94.7
97.2
53.8
105
0.41%
1.72%
61.5
92.0
0.5
1.39%
2.41%
101.5
105.3
58.8
125
0.74%
2.04%
74.7
130.5
0.7
2,08%
2.77%
128.
149.6
68.3
150
1.45%
2.74%
107.6
185.8
1.0
3.24%
3.69%
166.6
209.4
73.1
Table 3: Comparison to DE using handcrafted continuous decoder
TSP
CVRP
Avg. Gap
Runtime
Avg. Cost
Runtime
Method
n=20
u=50
n=100
n=20
n=50
n=100
n=20
R=50
a=100
n=20
n=50
n=100
Opte-Opt-DE
0.00%
0.02%
0.34%
10.5
21.5
55.1
6.14
10:40
20.8
41.0
94.7
Opt-DE
2.36%
14.06%
32.28%
11.0
22.0
56.0
6.32
12.18
23.97
21.1
41.1
95.2
mainly focus the ability to generalize to larger instances, because using model trained on small instances to tackle large-scale problems could be a viable option if training on large-scale instances shown in Table 2 Note that for the CVRP,
is too computationally expensive. The results report the gap to LKH3 to allow for better comparability sizes. For TSP and CVRP instances with 95, 100 and 105 nodes there is no notable performance difference, which shows the ability of our model to generalize well to instances that are slightly different than the training instances. This is an important aspect for the application of our method in practice. For instances with 125 and 150 nodes the performance is significantly worse. We note that impaired performance on instances that differ substantially from the instances seen during training is to be expected. However, this does not severely limit the applicability of our method because there are many scenarios in which the distribution of encountered instances does not change frequently.
the results over the different instance
4.7 ABLATION STUDY
We replace the learned decoding schema in CVAE-Opt-DE with a handcrafted decoder from the lit- erature to further evaluate what extent learning plays role in CVAE-Opt's performance. Opt-DE implements the decoding schema proposed by Bean (1944) while adopting all other components of carning-bbsse method. The decoder of Opt-DE takes in vector = [0 - 1|" that defines a per- mutation of the n nodes of a problem instance, which is constructed by sorting the nodes according their corresponding entry in z, i.e., node 2; corresponds to entry z; tour constructed by trying to visit the nodes in the order of the permutation. For the CVRP we use the same masking schema as for CVAE-Opt to avoid illegal tours. We limit the search time of Opt-DE the time needed by CVAE-Opt-DE and note that the handcrafted decoder is significantly faster than the learned decoder. The results are shown in 3 CVAE-Opt-DD outperforms Opt-DE on the TSP and CVRP for all instance sizes, with the difference being especially visible on larger problems.
CONCLUSION
We presented CVAE-Opt, a method that uses a variational autoencoder to learn a mapping of routing problem solutions points in continuous (latent) search space. The learned space be searched by any basic unconstrained continuous optimizer. The approach provides an interface between opti- mization and machine learning techniques, allowing traditional continuous optimization methods to search in a learned space. We show that our approach is able to learn a well-structured search space that enables a guided search by high-level, domain independent continuous optimizer. On TSP and CVRP instances, CVAE-Opt significantly outperforms slate-of-the-aa ML-based approaches. In the future, we will further investigate the properties of the learned search space and evaluate recent extensions to the VAE framework.
ACKNOWLEDGMENTS
The computational experiments in this work have been performed using the Bielefeld GPU Cluster.

---

Published as a conference paper at ICLR 2021
REFERENCES
David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver, 2006.
James C Bean. Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6(2):114-160, 1994.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 2016.
David Berthelot, Colin Raffel, Aurko Roy, and lan Goodfellow. Understanding and improving inter- polation in autoencoders via an adversarial regularizer. In International Conference on Learning Representations, 2018.
Sourodeep Bhattacharjee and Robin Gras. Estimation of distribution using population queue based variational autoencoders. In 2019 JEEE Congress on Evolutionary Computation (CEC), pp. 1406- 1414. IEFE, 2019.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. In Advances Neural Information Processing Systems, pp. 6278-6289, 2019.
Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks sequence modeling. arXiv preprint arXiv:1412.33555 2014.
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.
Unai Garciarena, Roberto Santana, and Alexander Mendiburu. Expanding variational autoencoders for learning and exploiting latent representations in search distributions. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 849-856, 2018.
Rafael Bimbar-Bo,,,,llli, Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sänchez-Lengeling. Dennis Sheberla, Jorge gguilera-Iparraguinn Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik Automatic chemical design using data-driven contin- uous representation of molecules. ACS central science, 4(2):268-277) 2018
José Fernando Gonçalves and Mauricio GC Resende. A parallel multi-population biased random- key genetic algorithm for container loading problem. Computers & Operations Research, 39 (2):179-190, 2012.
Keld Helsgaun. An extension of the Lin-Kernighhnn--elsgaan TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with a constrained variational framework. In International Conference Learning Representations, 2017.
John J Hopfield and David W Tank. Neural computation of decisions in optimization problems. Biological cybernetics, 52(3):141-152, 1985.
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.
Brian Ichter, James Harrison, and Marco Pavone. Learning sampling distributions for robot motion planning. In 20/8 IEEE International Conference Robotics and Automation (ICRA), pp. 7087- 7094. IEEE, 2018.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning, pp. 2323, 2018.
10

---

Published as a conference paper at ICLR 2021
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 2019.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op-
timization algorithms over graphs. In Advances in Neural Information Processing Systems, pp. 6348-6358, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412.6984 2014.
Diederik P. Kingma and Max Welling, Auto-cncoding variational bayes. In International Conference Learning Representations, 2014.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Matt J Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar variational autoen- coder. In International Conference on Machine Learning, pp. 1945-1954, 2017.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Liu. Neural architecture optimization. In Advances in neural information processing systems, pp. 7816-7827, 2018.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáe. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9839-9849, 2018.
Malte Probst, Franz Rothlauf, and Jömn Grahl. Scalability of using restricted Boltzmann machines for combinatorial optimization. European Journal of Operational Research, 256:368- 33333, Jan 2017. ISSN 0377-2217.
Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4):455-477 2006.
Vui Ann Shim, Kay Chen Tan, and Jun Yong Chia. Probabilistic based evolutionary optimizers in bi-objective travelling salesman problem. In Asia-Pacific Conference on Simulated Evolution and Learning. pp. 588-592 592. Springer, 2010.
Kihyuk Sohn, Honglak Lee, and Xinchen Yan. Learning structured output representation using deep conditional generative models. In Advances in neural information processing systems, pp- 3483-3491, 2015.
Rainer Storn and Kenneth Price. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 11(4):341-355 1997.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence sequence learning with neural networks. In Advances in Neural Information Processing Systems, pp. 1104-3112, 2014.
Huajin Tang, Vui Ann Shim, Kay Chen Tan, and Jun Yong Chia. Restricted boltzmann machine based algorithm for multi-objective optimization. In IEEE congress on evolutionary computation, pp. 1-8. IEEE, 2010.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pp. 2692-2700, 2015.
Robin Winter, Floriane Montanari, Andreas Steffen, Hans Briem, Frank Noé, and Djork-Amé Clev- ert. Efficient multi-objective molecular optimization continuous latent space. Chemical science, 10(34):8016-800 2019.
Byoung-Tak Zhang and Soo- Yong Shin. Bayesian evolutionary optimization using Helmholtz ma- chines. In International Conference on Purallel Problem Solving from Nature, pp. 827-836. Springer, 2000.
11

---

Published as a conference paper at ICLR 2021
A NETWORK ARCHITECTURE DETAILS
A.1 ENCODER
The encoder encodes a routing problem solution .0...., ST sequentially. The model is given the input features of the nodes -=--1 and Za, at decoding step & {I...., 7 separately from the problem representation of all nodes zo. ................................ Zn. For each of the inputs of the problem representation To. .o....., Zn. an embedding h; is created using linear transformation that is applied to all inputs separately and identically. For the separate input features of the nodes Is, and Ia different linear transformation is applied in a similar fashion to generate the embeddings V',,, and h., All learned embeddings have dimensionality of dj. and we set d, to 128 for all trained models.
The first recurrent neural network module RNN, receives the embedding V,,,, of the previously visited node in the solution s at each step t. The output h d contains information on the first t - elements of the solution. We implement all recurrent neural networks the model as gated recurrent neural networks (Chung et al., 2014).
All embeddings are used by the attention layer Att compute a single d, di-dimensional context vector e that describes all relevant t ho..... Iin The relevance of each input is determined based on the current encoding state given by ht, To compute the context vector c, first the n- dimensional alignment vector is computed that describes the relevance of each input:
ā softmar .... u
(3)
where
4 = A tanh(W [h, [11hh" h B1].
(4)
Here, 2 is a vector and W is a matrix with trainable parameters and 5." is used describe the concatenation of two vectors. Based on the alignment vector a the context vector e is generated:
agh4
(5)
The context vector e then used by the recurrent neural network module RNN2,, which is the main encoding component of the encoder. At each step & it is given the embedding of the t-th node in the solution sequence Fsy...., Esr in addition c. Its output h in the last iteration T encodes the complete sequence :.. Ext and is used in two separate linear transformations to calculate the d, dimennsiion vectors j and a. These vectors parameterize a multivariate normal distribution from which the latent variable is sampled using the reparameterization trick (Kingma & Welling 2014).
A.2 DECODER
The architecture of the decoder based on the model proposed in Nazari al. (2018). At each step t the model uses a pointer mechanism (Vinyals et al. 2015) to point towards the node that should be visited next. The decoder uses the same embedding, attention mechanism, and recurrent neural network RNN, as the encoder. The weights for these components are shared by the encoder and the decoder. addition to the inputs required to calculate c, the decoder also gets the latent variable as an input. The concatenation [z, c, 2xs- ,] is transformed by a linear layer to a da di-diiennioona vector e'. This vector provides the context to the pointing mechanism that calculates the output distribution over all actions based the node embedding embedding ho...., h,
po ( = poftmar(uo...... Un))
(6)
where
#4 B tanh ( (W c()) and the vector B and the matrix B contain trainable parameters.
12

---

Published as a conference paper at ICLR 2021
B SEARCH SPACE STRUCTURE ANALYSIS FOR ALL PROBLEM SIZES
Figure shows the absolute cost difference and the euclidean distance the sampled solutions to the reference solution (i.e., the best solution found in random search of 1,000 solutions) for all problem classes.
Abs. casl ditt to bost Sound salution
Abx coel dill. best found sinntio
TSP20
TSP50
TSP100
3.0
2.0
1.0
6.0
0.0
0.00
6.0
0.1
0.1
0.2
0.3
200
5.0
distrnnc
Faelidian distanne best
Abs. con cilt to best Sound salation
cill to lett locard solution
CVRP50
3.0-
3.0
3.0-
2.0
1.0-
3.0-
1.0
0.0
0.0
Euelidenn Clraanoc to best Souzad solutioo
Exciddan distance to best found nolution
0.1
0.2
0.5
2.0
Abs.
Enclidomm distance best found solution
0.2
Figure 9: Solution quality vs. distance in the latent search space
13


Reviews:
[{"review_id": "W-3afF4djK5", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose an algorithm for routing problems by (1) using conditional variational autoencoder to learn a latent space for solutions, and (2) performing black-box continuous optimization such as evolutionary algorithms in the space. The proposed method outperforms existing neural-based methods on a benchmark of the traveling salesmen, and the capacitated vehicle routing problem.\n\nThe presentation and writing of the paper are excellent. I really like the intro and related work section where the authors have done a comprehensive survey and position their work among existing ones.\n\nAlthough the method is very neat and general, the idea of learning a latent space for solutions to combinatorial search problems is not new. It has been investigated in both continuous control\\cite{ichter2018learning} and drug design\\cite{gomez2018automatic}. In particular, \\cite{ichter2018learning} also uses a conditional variational autoencoder to address the issue brought by different problem instances. The authors should discuss more on the challenges of the current problem, why previous approaches cannot apply here, and focus on how to deal with the challenges, otherwise, the contribution will be weak.\n\nAlso in the experiment section, it would help the readers understand the approach better by including ablation studies such as applying evolutionary and random search methods directly in the solution space. There is no need to design sophisticated mutation strategies that involve domain knowledge. Simple heuristics will suffice here.\n\nIn general, I think this is a borderline paper mostly due to its weak contributions. I will consider raising the score if the authors address the issues well.\n\nAdditional question: what is the problem distribution? how do you generate them?\n\n\n\n@inproceedings{ichter2018learning,\n  title={Learning sampling distributions for robot motion planning},\n  author={Ichter, Brian and Harrison, James and Pavone, Marco},\n  booktitle={2018 IEEE International Conference on Robotics and Automation (ICRA)},\n  pages={7087--7094},\n  year={2018},\n  organization={IEEE}\n}\n\n\n@article{gomez2018automatic,\n  title={Automatic chemical design using a data-driven continuous representation of molecules},\n  author={G{\\'o}mez-Bombarelli, Rafael and Wei, Jennifer N and Duvenaud, David and Hern{\\'a}ndez-Lobato, Jos{\\'e} Miguel and S{\\'a}nchez-Lengeling, Benjam{\\'\\i}n and Sheberla, Dennis and Aguilera-Iparraguirre, Jorge and Hirzel, Timothy D and Adams, Ryan P and Aspuru-Guzik, Al{\\'a}n},\n  journal={ACS central science},\n  volume={4},\n  number={2},\n  pages={268--276},\n  year={2018},\n  publisher={ACS Publications}\n}\n\n\nUpdate after rebuttal:\nThanks for the response! I think it resolves my concerns on novelty and evaluation. Hence I raise my score to 6.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QSCqvwc9hvH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method to learn a continuous latent space via CVAE to represent solutions to routing problems. Combined with differentiable evolution search algorithms, one can search in the learned latent space for solutions to new problem instances at test time. The proposed method is evaluated on two classes of routing problems: TSP and CVRP. Results show better performance in terms of objective values and runtime. They are also competitive with established expert-designed algorithms such as LKH3.\n\nPositives:\n1. The proposed method is novel. The specific algorithm to realize the idea of learning continuous latent spaces is sensible and easy to understand, thanks to clear writing.\n\n2. A continuous latent space enables one to use existing tools in continuous optimization, as this paper demonstrates via two examples: differentiable evolution and random search.\n\n3. The evaluations on two practically relevant routing problems demonstrate the advantage of the proposed method. The experimental section includes useful insight into hyperparameter selection and interpretations of learned latent spaces.\n\nNegatives:\n1. Comparison with Joshi et al. (2019) should be included for TSP as well, especially their beam search variants. Given a major benefit of the proposed method is to enable search, comparing with beam search can better evaluate the practical advantage of the proposed method. The sampling procedure used in AM by Wool et al. (2019) improves solution quality but is not a direct search procedure.\n\n2. The problem size is relatively small with the largest problems having 100 nodes. I expect the proposed method, with the resulting continuous latent space, achieves larger improvements for larger problem instances. Can the authors consider larger scale experiments?\n\nQuestion:\n1. For symmetric breaking, does the symmetrical solution to each input problem change between epochs?\n\n2. Is it possible to employ gradient-based optimization algorithms in the learned latent space?\n\n=====================\nPost-rebuttal comments:\n\nThank the authors for the detailed responses and revised submission. My concerns have been adequately addressed and I raised my score to 7.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PVDloJ7KRCc", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall great work and highly readable, as reviewer I am leaning to accept\n\n##########################################################################\n\nSummary:\n\n \nThe paper presents a way of solving routing problems (which are discrete and highly combinatorial)\nby optimising the input to an instance-specific mapping from a continuous vector space to the space of solutions for that particular instance (desiring high objective value solutions).\nThe mapping is obtained from masked autoregressive sampling with a decoder trained as part of a conditional VAE.\n\n##########################################################################\n\nReasons for score: \n\n \nOverall, I vote for accepting. The idea presented is neat and seems to work well in the instance size range presented . I have one major concern about generalisation in problem-instance sizes (expanded below in Cons 1). The paper is readable. The experiments could be improved and I make suggestions for that. Hopefully the authors can address my concern in the rebuttal period. \n\n \n##########################################################################Pros: \n\nPros:\n\n1. The paper leverages a re-parametrization of the search space to make search better and in this case to even allow unconstrained continuous optimization methods for the problem of routing in a way that successfully generalizes to unseen instances (the best solutions to routing problems are problem-specific). \n\n \n2. The paper is clear and readable. \n\n \n##########################################################################\n\nCons: \n\n\nI have not taken into account points 2-5 for making review score decisions, but I believe they should be addressed in a camera-ready worthy version of the paper\n\n\n1. It isn't clear to me if the model is trained (and tested) on instances of varying sizes or fixed size. Generalising/extrapolating to unseen problem-instance sizes is really important.\n  + If the approach is size-specific then any unseen problem-instance size at test time will require generating new data and training, which would limit the impact of the approach.\n  + If the approach isn't size specific (from what I understood in the Appendix A it isn't) what is the training instance size distribution? From the section 4 wording I understood that the sizes are fixed, but I could have misunderstood.\n    - One possibility for showing size-generalisation/extrapolation could be training on one size (e.g. n=50) and testing on the other two sizes (e.g. n=20 and n=100). (Edit: the authors have done this)\n\n2\u0010. There is the implicit claim that learning helps, but there is no ablation/comparison to a randomly initialised model, I expect it to do really badly, but even in that case it would only help to show that it is the learning/training component (and not the architecture's inductive biases alone) that make the approach successful. Running CVAE-Opt-DE with a randomly initialised model and adding that to Table 1 would be great. (Edit: the authors have addressed this)\n3. The authors show their approach can be used by any unconstrained continuous optimization algorithm by evaluating one and a variation of it. There is the possibly implicit claim of \"any optimization algorithm can be used and still get great results\" and it might merit having optimization method different-enough from the other two. (Edit: the authors have explained this)\n4. The current decoding takes O(solution_size * problem_size) time, as the problem-instance is passed at each time-step, this will limit the scalability to large input sizes. (Edit: the authors have clarified this is fine in the subdomain they are targeting)\n5. It is not clear to me if Figure 5 shows one representative per equivalence class, or possibly more than one. (Edit: the authors have clarified)\n\n\n##########################################################################\n\nRandom thoughts\n\nBeing able to function-approximate the decoding plus measuring objective value, would allow gradient-based planning, and make the approach even better, Figure 5 suggest we might be able to do a linear/quadratic function of the latent search space points to the objective values (but even then variance could be too high). Maybe a cheaper alternative to know if this is worthwhile is plotting for each pair of solutions in Figure 5 the distance in x-axis and the cost-diff in y-axis (a per-solution view instead of being histogram aggregated) \n\n##########################################################################\n\nQuestions during rebuttal period: \n\nPlease address and clarify the cons above ", "extra_scores": {}, "extra_text": {}}, {"review_id": "LJ_bq9H-PpA", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "$\\textbf{Summary.}$ This paper proposes a new approach to solve routing problems based on (1) training a variational autoencoder (VAE) to model the optimal solution of problems (i.e., supervised learning) and (2) applying continuous search methods for decoding at test time. While I think the idea of this paper is promising, it is limited in the sense that (1) the method is not particularly novel, (2) the VAE model relies on supervised learning for training, (3) the experiments are limited to small-scale settings, and (4) the proposed method does not show any promise over the \"traditional\" solvers, e.g., Concorde or LKH3. \n\n$\\textbf{Pros.}$ \n- I think the idea of transforming the combinatorial search problem into a continuous search problem is interesting. This direction has not been considered in the literature of using DNNs for combinatorial optimization.\n- The proposed framework can easily be generalized to combinatorial optimization problems other then routing problems, e.g., minimum vertex cover. \n\n$\\textbf{Cons.}$\n- The proposed framework is not particularly novel when compared to the existing works on de novo drug design using DNNs (which is also a combinatorial optimization). The paper mentions how routing problems are different from de novo drug design tasks since they require the DNN-solver to encode context of the given problem. However, this does not make the problem much more challenging and the paper simply uses conditional VAE to take care of the context encoding. \n- Importantly, the proposed framework use supervised learning for training the model and requires extracting optimal solutions from the training graphs using existing solvers. This severely limits applicability of the proposed framework. In comparison, (Kouter et al. 2019) trained the AM model using reinforcement learning to motivate DNNs for solving combinatorial problems where exact solvers do not exist. \n- For small scale instances (considered in the experiments), exact solvers can usually find solution better than the heuristics. I encourage the authors to provide more results on large-scale experiments, since this is where non-exact solvers are needed. This is especially significant since it is computationally intractable to extract optimal solutions from large-scale problems. How would the proposed method handle this case?\n- I think the proposed framework lacks motivation, since the proposed method does not show much promise over the traditional solvers such as Concorde or LKH3. This is especially significant since the proposed framework requires using traditional solvers to extract optimal solutions on the training graphs. In what situations would users be encouraged to use the proposed framework?\n- In the experiments, I think the authors should add a baseline proposed by (Lu et al. 2020) since they also considered using neural networks to solve the routing problems. While they use certain domain-specific components, I think the proposed framework also relies on domain knowledge (since they require exact solvers for training).\n- I suggest adding a reference to (Winter et al. 2019), who proposed to use swarm optimization on the latent space of VAE for molecular optimization.\n\n$\\textbf{References.}$\n\n(Winter et al. 2019) Efficient Multi-Objective Molecular Optimization in a Continuous Latent Space, Chemical science 2019\n\n(Lu et al. 2020) A Learning-based Iterative Method for Solving Vehicle Routing Problems, ICLR 2020\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a learning based approach for solving combinatorial optimization problems such as routine using continuous optimizers. The key idea is to learn a continuous latent space via conditional VAE to represent solutions and perform search in this latent space for new problems at the test-time. The approach is novel and experiments showed good results including ablation analysis. 

Reviewer comments are adequately addressed during the response phase and I find the changes satisfactory. Overall, this is a good paper and I recommend accepting it.

One last comment: It would be a great addition if the paper could add discussion about the applicability of this approach to arbitrary combinatorial optimization problems and what design choices are critical to come up with an effective instantiation.
Decision: Accept (Poster)