Combinatorial Optimization with Policy Adaptation using Latent Space Search
Authors: Felix Chalumeau
Shikha Surana
Clément Bonnet
Nathan Grinsztajn
Arnu Pretorius
Alexandre Laterre
Thomas D Barrett
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement Learning
Combinatorial Optimization
TSP
CVRP
JSSP
TL;DR: A novel reinforcement learning approach for combinatorial optimization that adapts a set of diverse and specialized policies at test time through a search in a latent space.

Abstract: Combinatorial Optimization underpins many real-world applications and yet, designing performant algorithms to solve these complex, typically NP-hard, problems remains a significant research challenge. Reinforcement Learning (RL) provides a versatile framework for designing heuristics across a broad spectrum of problem domains. However, despite notable progress, RL has not yet supplanted industrial solvers as the go-to solution. Current approaches emphasize pre-training heuristics that construct solutions, but often rely on search procedures with limited variance, such as stochastically sampling numerous solutions from a single policy, or employing computationally expensive fine-tuning of the policy on individual problem instances. Building on the intuition that performant search at inference time should be anticipated during pre-training, we propose COMPASS, a novel RL approach that parameterizes a distribution of diverse and specialized policies conditioned on a continuous latent space. We evaluate COMPASS across three canonical problems - Travelling Salesman, Capacitated Vehicle Routing, and Job-Shop Scheduling - and demonstrate that our search strategy (i) outperforms state-of-the-art approaches in 9 out of 11 standard benchmarking tasks and (ii) generalizes better, surpassing all other approaches on a set of 18 procedurally transformed instance distributions.

Combinatorial Optimization with Policy Adaptation using Latent Space Search
Felix Chalumeau"
Shikha Surana" InstaDeep s. surana@instadeeppcom
InstaDeep chalumea@@instadeppppoo com
Clément Bonnet
Nathan Grinsztajn InstaDeep n. griinstajnninssadepppp.. com
InstaDeep
c. boonet@instadeep.....
Arnu Pretorius
Alexandre Laterre
InstaDeep
InstaDeep
a pretoriusdinstadeppccom
a.laterre@instadeeppccm
Thomas D. Barrett
InstaDeep t. www.eettiinttadeeppp..oo com
Abstract
Combinatorial Optimization underpins many real-world applications and yet, de- signing performant algorithms to solve these complex, typically NP-hard, problems remains significant research challenge. Reinforcement Learning (RI.) provides a versatile framework for designing heuristics across broad spectrum of problem domains. However, despite notable progress, RL has not yet supplanted industrial solvers as the go-to solution. Current approaches emphasize pre-training heuristics that construct solutions but often rely on search procedures with limited variance, such stochastically sampling numerous solutions from single policy ploying computationally expensive fine-tune lnn-ttnnng of the policy on individual problem instances. Building the intuition that performant search inference time should be anticipated during pre-training, we propose COMPASS, novel RI. approach that parameterizes distribution of diverse and specialized policies conditioned a continuous latent space. We evaluate COMPASS across three canonical problems Travelling Salesman, Capacitated Vehicle Routing, and Job-Shop Scheduling and demonstrate that our search strategy (i) outperforms state-of-the-art approaches in 9 out of 11 standard benchmarking tasks and (ii) generalizes better, surpassing all other approaches on a set of 18 procedurally transformed instance distributions.
1 Introduction
Combinatorial Optimization (CO) has a wide range of real-world applications, from transporta- tion (Contardo al., 2012) and logistics (Laterre et al., 2018), energy (Froger et al., 2016). Solving a CO problem consists of finding an ordering, labelling or subset of elements from finite, discrete that maximizes (or minimizes) given objective function. As the number of feasible solutions typically grows exponentially with the problem size, CO problems are challenging (often NP-hard) solve. As such, significant work goes into designing problem-specine heuristic approaches that,
Equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

whilst not guaranteeing the optimal answer, can often work well in practice. Reinforcement Learning (RL) offers a domain-agnostic framework to learn heuristics and has been successfully applied across a range of CO tasks (Vinyals et al., 2015; Deudon et al., 80; Mazyavkina et al., 2021).
Concretely, leading RL methods typically train a policy to incrementally construct solution one element at a time. However, whilst most efforts have focused on improving the one-shot quality of these construction heuristics (Kool al., 2019; Kwon et al., 2020; Grinsztajn et al., 2022), intuitively appears impractical to reliably produce the optimal solution to NP-hard problems within a single construction attempt. Consequently, competitive performance has to rely on combining a pre- pre-trained policy with an additional search procedure. Nevertheless, this crucial aspect is often implemented using simple procedures such as stochastic sampling (Kool et al., 2019; Kwon et al., 2020; Grinsztajn et al., 2022), beam search (Steinbiss et al., 1994) or Monte Carlo Tree Search (MCTS) (Browne et al., 2012). An alternative approach, representing the current state-of-the-ard for search-based RI (Bello et al., 2016; Hottung et al., 2022), is to actively re-train the heuristic on each new problem instance; however, this comes with clear computational and practical limitations. Strikingly, neither of these approaches pre-trains the policy in a way that could enable fast and efficient inference time search: rather current approaches typically completely decouple both. The absence of an efficient search strategy is even more detrimental when the test instances are out of the distribution (OOD) used to train the policy, as this may cause a large difference between the learned policy and the policy leading to the optimal solution.
In this work, we aim to overcome the current limitations of search strategies used in RL when applied to CO problems. Our approach is to learn latent space of diverse policies that can be explored at inference time in order to find the hest-performing strategies for a given instance. This updates the current paradigm by enabling sampling from policy space at inference time rather than constantly sampling the same policy (or set of policies) with stochasticity. We introduce COMPASS COMbinatoiial optimization with Policy Adaptation using Latent Space Search. COMPASS effectively creates an infinite set of diverse solvers by using a single conditioned policy and sampling the conditions from a continuous latent space. The training process encourages subareas of the latent space to specialize to sub-distributions of instances and this diversity is used at inference time to solve newly encountered instances.
We evaluate COMPASS on three popular CO problems: Travelling Salesman Problem (TSP), Capaci- tated Vehicle Routing Problem (CVRP) and Job-Shop Scheduling Problem (ISSP). After training on a distribution of fixed-sized instances for each problem, we evaluate our method on both in- and out-of-distributtin test sets, We find that simple search strategies requiring no re-training provide both rapid and sustained improvement of the instance-specific policy, with COMPASS establishing a new state-of-the-arr across all problems in this setting. Thanks to the diversity provided by its latent space, COMPASS achieves high performance even without a search budget and achieves comparable or better results than current leading few-shot methods.
Concretely, our work makes the following contributions: (i) We introduce COMPASS which leverages a latent space of diverse and specialized policies to effectively solve CO problems. (ii) We show that COMPASS allows for the efficient adaptation of instance-specifer policies without re-training or sacrificing zero-shot performance. (iii) Experimentally, our approach is found to represent new state-of the for RL- CO methods across all our considered problem types, achieving superior performance in 27 out of 29 tasks. (iv) We release fast and performant implementations of our method and its main competitors, written in JAX. We also provide all of our test sets including our procedurally transformed problem instances for easier comparison in future work.
2
Related work
Construction methods for CO Construction approaches in RL for CO incrementally build solution by selecting one element at a time. After Hopfield and Tank (1985) first applied neural networks to TSP, Bello al. (2016) extended these efforts by proposing to learn heuristics with RL using a Pointer Network (Vinyals et al., 2015) combined with an actor-critic framework. This approach was extended by Deudon et al. (2018) who added an attention-based city encoder, which was subsequently further extended by Kool et al. (2019) to use general transformer architecture (Vaswani et al., 2017). The transformer has since become the standard model for a range of CO problems and is also used in this work. Kim et al. (2022) builds on Kool et al. (2019) by leveraging
2

---

symmetries of routing problems during training. Even though the majority of these construction approaches have focused on routing problems, numerous works have also tackled other classes of CO problems, especially on graphs, like Maximum Cut (Dai et al., 2017; Barrett et al., 2020), or Job Shop Scheduling Problem (ISSP), for which Zhang et al. (2020) proposed Graph Neural Network (GNN) approach. A broader scope of (non-construction) approaches can be found in Appendix K.
Improving solutions at inference time As it is unlikely that the first solution generated by construction heuristic is optimal, a popular approach consists in sampling various trajectories during inference for the same CO problem. POMO (Kwon et al., 2020) uses one policy rolled out on several versions of the same problem, while considering different starting points or symmetries, to create diverse trajectories and select the best one. Choo et al. (2022) proposes an efficient search guided by simulations, but cannot take advantage of a large inference budget by itself. EAS (Hottung et al., 2022) adds on POMO by fine-tuning a subset of the model parameters at inference time using gradient descent. However, the new solutions are biased toward the underlying pre-trained policy and can easily be stuck in local optima. Instead, MDAM (Xin et al., 2021) and Poppy (Grinsztajn et al., 2022) employ a population of agents, all of which are simultancously rolled out at inference time. MDAM trains these policies to select different initial actions, whereas Poppy utilizes loss function designed to specialize each policy on specific subsets of the problem distribution. Despite demonstrating promising performance, these approaches training, which remains fixed. Such a limitation quickly diminishes the benefits of additional solution candidates sampled from the population. Our method COMPASS uses the same loss as Poppy, but, unlike their approach and that of MDAM, COMPASS is not bound to a specific number of specialized policies. Moreover, its latent space makes it possible to add additional search mechanisms over the policy space, ensuring better solutions over time. CVAE-Opt (Hottung et al., 2021), 1), akin to our method. uses a latent space for solving routing problems. however, it has several differences. First, COMPASS is trained end-to-end with RL, hence does not necessitate pre-solved instances. Second, CVAE-Opt requires training an additional recurrent encoder for (instance, solution) pairs, whereas COMPASS uses the latent space to encode a distribution of complementary policies and can be easily applied to pre-train models. Overall, COMPASS significantly outperforms CVAE-Opt while having shorter runtime.
constrained by the number of policies used during
3 Methods
3.1 Preliminaries
Formulation The goal of a CO problem is to find the optimal labeling of a set of discrete variables that satisfies the problem's 's constraints. In RL, a CO problem can be formulated as a Markov Decision Process (MDP) defined by M = (S, A. R, T. 7: H). This includes the state space S with states 8; E S. action space with actions a; E A, reward function R: S A - R, transition function T(s++1 /s: a;), discount factor 7 E [0, 1], and horizon H which denotes the episode duration. The state of a problem instance represented as the (partial) trajectory or set of actions taken in the instance, and the next state 1 is determined by applying the chosen action ag to the current state 8t. An agent is introduced in the MDP to interact with the CO problem and find solutions by learning a policy : S + A. The policy is trained to maximize the expected sum of discounted rewards to find the optimal solution, and this is formalized as the following learning objective:
r = argmax E >n' 7² (())),a)..
3.2 COMPASS
Recall our intuition that no single policy will reliably be able to solve all instances of an NP-hard CO problem in a single inference pass. Two primary approaches to address this are the inclusion of inference time search and the deployment of a diverse set of policies to increase the chance of opar-optimal strategy being deployed. This work aims to unify and extend these approaches by training an infinitely large set of diverse and specialized policies that can subsequently be searched at inference time.
To achieve this, we propose that a single set of policy parameters condition not just on the current observation, but also on samples drawn from a continuous latent space. The training objective
3

---

A. Training
B. Inforonce
E. Baaritte
Reloot
Pe oue
Canernta Solutton
Intlates
Sorepla
Exalutt Polidie
Sample
3. Update
Locty
PENHOONCE
Hepeet
Tran Besr
Figure 1: Our method COMPASS is composed of the following two phases. A. Training- the latent space sampled to generate vectors that the policy can condition upon. The conditioned policies are then evaluated and only the best one is trained to create specialization within the latent space. B. Inference at inference time the latent space searched through an evolution strategy to exploit regions with high-perfon nigh-performing policies for each instance.
then encourages this latent space of policies to be diverse (generate a wide range of behaviors) and specialized (these behaviors are optimized for different types of problem instances from the training distribution). This latent space can then be efficiently searched during inference to find the most performant policy for given problem instance. In this section, describe in detail the realization of this approach, which we call COMPASS (COMbinatorial optimization with Policy Adaptation using Latent Space Search). In Fig. 1, we provide illustrated overview of COMPASS.
Our approach offers several key advantages over traditional techniques. Compared to methods that directly train multiple, uniquely parameterized policies (Xin et al., 2021; Grinsztajn et al., 2022), training a single conditional policy can, in principle, provide a continuous distribution of an infinite number of policies. Moreover, our approach mitigates the significant training and memory overheads associated with training a population of agents. Compared to methods that rely on brute-force sampling (Kool et al., 2019; Kwon et al., 2020; Grinsztajn al., 2022) expensive (Hottung et al., 2022), our training process produces a structured latent space (where similar policies found near to each other) that permits principled search during inference.
Latent space The latent space defines the set of policies that our model can condition itself upon. Importantly, do not learn the distribution of this space, but rather select a space from which we sample during training. In practice, we use a latent space with 16 dimensions bounded between -1 and 1, and use uniform sampling prior.
prior distribution over the
Architecture COMPASS is agnostic to the network architecture used, so long as the resulting policy is, in some way, conditioned on the vector sampled from the latent space. This can be achieved in numerous ways, from directly concatenating the vector to the input observation to conditioning queries, and values in the self-attention models commonly used for CO. We refer to Appendix D for further details about the architectures used in this work and how the latent vector is used to condition them. Whilst is possible to train COMPASS from scratch, we found that it was simple and efficient to adapt pre-trained singlc-policy models. To do this, we acro-initialize any additional weights corresponding to the sample latent vector such that it has no impact at the start of training. In practice, we adapt single-agent architecture designed for few-shot inference in all of our problem settings; POMO (Kwon et al., 2020) for TSP and CVRP, and a similar architecture taken from Jumanji (Bonnet et al., 2023) for JSSP (we also considered the current SOTA model L2D (Zhang al., 2020), however, we found that the model from Jumanji already outperformed this approach). Full network details can be found in Appendices D. (TSP & CVRP) and D.2 (JSSP).
Training The training procedure aims to specialize subareas of the latent space to sub-distributions of problems by training the policy solely on latent vectors that achieve the best performance on a given problem. At each training step, we uniformly sample a set of N vectors from the latent space and condition the policy on each vector resulting in N conditioned policies. After evaluating each policy

---

on the problem instance, we train the best policy (i.e. the policy conditioned on the best- perffomnrnnn
latent vector) on the instance. The model is updated using the gradient of our objective as given by
V compasss B.pD B ( (.., Vo log (To (x )R,- (...-BB.)).
(I)
where D is the data distribution, Pa the latent space, 2, a latent vector, Te the conditioned policy, To the trajectory generated by policy πa conditioned on vector 2; and has the corresponding reward R2 i" is the index of the best performing latent vector (in the sampled set) and is expressed as i" = arg [I,,] R. and lastly, Bp is the baseline, inspired by Kwon et al. (2020). Full details of the algorithmic procedure can be found in Appendix F. Notably, our work is the first to create a specialized and diverse set of policies represented by a continuous latent space by only training the best-performing vector for each problem instance.
key training hyperparameter is the number of condition vectors sampled during evaluation. More conditioned policies results in increased certainty that the best-performing vector in the sampled set of conditions is the best-perfore pest-performing vector in the latent space. Therefore, increasing the number of sampled conditions increases the likelihood of training the true best latent vector for the given problem instance, rather than a potentially suboptimal vector. More details (including training times and environment steps) are reported in Appendix F.
Inference-time search Given the latent space of diverse, specialized policies obtained by training COMPASS, at inference time, we apply a principled search procedure to find the most performant strategies. Our desired properties for a search procedure are that it should be simple, capable of rapid adaptation and robust to local optima. As such, evolutionary strategies are an appropriate approach. Specifically, we use Covariance Matrix Adaptation (CMA-ES, (Hansen and Ostermeier, 2001)). CMA-ES uses multivariate normal distribution to sample vectors and iteratively updates the distribution's 's mean to increase the expected performance of sampled vectors (i.e. the quality of the solution found by the policy corresponding to each vector). The covariance also adapted over time, either for exploration (high values, broad sampling) or exploitation (small values, focused sampling).
For given problem instance, there may be multiple high-performance policies, therefore use several independent CMA-ES components in parallel. To ensure that those components explore distinct areas of the space (or least, take different paths), we compute Voronoi Tesselation (Du et al., 1999) of the latent space and use the corresponding centroids to initialize the means of the CMA-ES components. This method proves be robust, easy tune, and fast, and requires low memory and computation budget, making it the perfect candidate for efficient adaptation at inference time. In our experimental section (4.3), we present an analysis of our latent space and how it is explored by CMA-ES. Details and considered alternatives can be found in Appendix E.4.
4 Experiments
We evaluate our method on three problems Travelling Salesman (TSP), Capacitated Vehicle Routing (CVRP), and Job Shop Scheduling (JSSP) widely used to assess RL-based methods for CO (Deudon et al., 2018; Kool et al., 2019; Grinsztajn et al., 2022; Hottung et al., 2022). In Section 4.1, we evaluate COMPASS in the standard setting used by other methods from the literature and report results on each problem type. In Section 4.2, we assess the robustness of methods by evaluating them on instances of TSP and CVRP that are procedurally transformed using the approach developed by Bossek et al. 92019). In Section 4.3, we analyze the methods' search strategies; in particular, we provide insights about COMPASS' latent space and how it is navigated by CMA-ES at inference time. Figure 2 provides a radar plot overview of our aggregated experimental results across six performance categories of interest: (1) in distribution instances, OOD instances with different levels of distribution shift (2) small, (3) medium and (4) large, (5) large instance sizes as well as (6) few-shot performance. Our results highlight the strengths and weaknesses of each approach and in particular, the versatility and superiority of COMPASS.
We compare COMPASS to a suite of leading RL methods and industrial solvers. Across all problems we provide baselines for EAS (Hottung et al., 2022); the current SOTA active-search RL method that fine-tunes the policy on each problem instance, and Poppy (Grinsztajn et al., 2022); the current SOTA active-search RL method that stochastically samples from a fixed population of
Baselines
5

---

pre-trained solvers. For routing problems (TSP and CVRP), we also provide results for POMO (Kwon al., 2020); the leading single-agent, one-shot architecture on which EAS and Poppy are built, and LKK (Helsgaun, 2017); leading industrial solver. We also report results of TSP-specifie industrial solver Concorde (Applegate et al., 2006). For JSSP, we provide results for L.2D (Zhang et al., 2020); the leading single-agent, one-shot architecture. We also provide results for the attention-based model proposed in Jumanji (Bonnet et al., 2023) that proved to outperform L2D. Finally, we report the results of Google OR-Tools (Perron and Furnon, 2019); the reference industrial solver for JSSP.
Training As our method capable of adopting initial parameters from a pre-trained model, we re-use publicly available checkpoints of POMO (details in Appendix H) as the starting point for COMPASS on TSP and CVRP. For JSSP, we found attention-basee model from Bonnet et al. (2023) outperforms L2D and hence choose it to be the reference single-agent architecture. We train the model and use the same trained checkpoints for all methods. We then train COMPASS until convergence on the same training distribution as that used to train the initial checkpoint. For TSP and CVRP these are problem instances with 100 locations uniformly sampled within a unit square. For JSSP, we use the same training distribution used in EAS, which an instance with 10 jobs and machines, and maximum possible duration of 98. single set of hyperparameters is used across all problems, with full training details provided in Appendix G.
Inference When evaluating active-search performance, each method is given a fixed budget of 1600 attempts similar to Hottung et al. (2022); Grinsztajn et al. (2022) where each attempt consists of one trajectory per possible starting point. This approach is used to enable direct comparison to POMO and EAS which TSP and CVRP, we do not use the "augmentation trick"; where the same problem is solved multiple times by rotating the coordinate frame make it appear different and thus generate additional diverse trajectories. This trick was used in a few baselines from prior work, however, we refrain from using it in the main results of this work for two reasons: (1) it a domain-specific trick mainly applicable routing problems and (2) it significantly increases the required computational budget. We nevertheless provide some results in both settings ease comparison with previous work. Overall, the trajectory budget is exactly the same as the one used in Grinsztajn et al. (2022); Hottung et al. (2022). Note that expressing the budget in terms of trajectories gives an advantage EAS, which uses more time, memory, and computation due to the backpropagations used to update the policy during the search.
rollouts from all starting points each step. For the main results
In Distribution
In Distribution Instances drawn from the train- ing distribution (see first cols. in Tables la to Ic). Larger Instances Instance with a larger size than the training data. See generalization in Ta- bles 1a Ic.
Faw-Shot
Instances
Small/Medium/Large Shift been procedurally mutated to out of the training distribution. Detailed results in Fig. 3.
Instances that have
Large Shift
S mall
Few-Shot The standard benchmark with a lower budget (typically 10% of the usual). Numerical results in Appendix
Shift
Medium Shift Poppy
(ours)
Figure 2: Performance COMPASS and the main baselines aggregated across several tasks over three problems (TSP, CVRP, and JSSP). For each task (problem type, instance size, mutation power), we normalize values between 0 and (corresponding respectively). Hence, all tasks have the same impact on the aggregated metrics. COMPASS surpasses the baselines on all of them, showing its versatility for all types of tasks and in particular, its generalization capacity.
the worst and best performing RI. method,

---

Table 1: Results of COMPASS against the baseline algorithms for (a) TSP, (b) CVRP, and (c) JSSP problems, The methods are evaluated on instances from training distribution as well as on larger instance sizes to test generalization.
(a) TSP
Training distr. 100
Generalization
200
Method
Ohj.
Gup
Time
Obj.
Gap
Time
Ohj.
Gopp
Time
Ohj
Gup
Time
Concorde
7.765
0. 0.000%
82M
8,583
0.000%%
12M
9.346
0.000%
17M
10.687
0.000%
31M
LKH3
7.765
0.0000%
811
8.583
0.000%
73M
9.346
0.000%
99M
10.687
0.000%
3H1
POMO (greedy)
7.796
0.404%
37S
8.635
0.607%
68
9.440
1.001%
10S
10.933
2.300%
218
POMO (sampling)
7.779
0.185%
2H
8.609
0,299%
20M
9.401
0.585%
32M
10.956
2.513%
70M
Poppy 16
7.766
0.013%
2H
8,587
0.050%
20M
9.359
0.141%
32M
10.795
1.007%
70M
EAS
7.779
0.176%
7H
8.601
0.252%
62M
9.382
0.381
2H
10.758
0.660%
210M
COMPASS (ours)
7.765
0.002%
2H
8,586
0.036%
20M
9.354
0.083%
32M
10.724
0.348
70M
(b) CVRP
Training distr.
Generalization
100
125
Method
Obj.
Gap
Time
Obj-
Gap
Time
Obj.
Gap
Time
Obj
Gap
Time
LKH3
15.65
0.000%
0.000%
19.22
0.0000%
0.000%
POMO (greedy)
15.874
1.430%
2M
17,818
1881%
<IM
19.750
2.757%
1M
23.318
5.992%
2M
POMO (sampling)
15.713
0.399%
4H
17.612
0.642%
43M
19.488
1.393%
1H
23.378
6.264%
100M
Poppy 32
15.663
0.084%
4H
17.548
0.276%
42M
19.421
1.044%
1H
23.352
6.144%
100M
EAS
15.661
0.068%
13H
17.517
0.094%
2H
19.285
0.341
4H
22.264
1.120%
7H
COMPASS (ours)
15,594
40.361%
0.064%
42M
19.313
0.485%
22.462
2.098%
(c) JSSP
Training distr.
Generalization
10 x 10
x 15
20 x 15
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
OR-Tools
807.6
0.0%
37S
1188.0
0.0%
3H
1345.5
0.0%
80H
L2D (sampling)
871.7
8.0%
811
1378.3
16.0%
2511
1624.6
20.8%
4011
Single
862.1
6.7%
3H
1302.6
9.6%
5H
1503.0
11.7%
SH
Poppy
849.7
5.2%
3H
1290.4
8.6%
SH
1495.7
11.2%
8H
EAS
858.4
6.3%
511
1295.2
9.0%
911
1498.0
11.3%
1111
COMPASS (ours)
845.5
4.7%
3H
1282.8
8.0
SH
1485.6
10.4%
8H
Code availability We release the code used train our method and run all baselines. We also make our checkpoints available for all three problems, along with the datasets necessary to reproduce the results. To ensure fair comparison and extend our evaluation to new settings, we reimplemented all baselines within the same codebase. For the three problems, we used the JAX (Bradbury et al., 2018) implementations from Jumanji (Bonnet et al., 2023) to leverage hardware accelerators (e.g. TPU). Our code is optimized for TPU v3-8, which is the hardware used for our experiments.
4.1 Standard benchmarking on TSP, CVRP, and JSSP
We evaluate our method on benchmark sets frequently used in the literature (Kool et al., 2019; Kwon et al., 2020; Grinsztajn et al., 2022; Hottung et al., 2022). Specifically, for TSP and CVRP, we use datasets of 000 instances drawn from the training distribution, with the positions of 100 cities/customers uniformly sampled within the unit square, and three datasets not seen during training, each containing 1000 problem instances but with larger sizes: 125, 150 and 200, also generated from uniform distribution over the unit square. We use the exact same datasets as in the literature.
Results The average performance of each method across all problem settings are presented in Ta- ble 1. We find that COMPASS demonstrates superior performance 9 out of the 11 test sets considered. Moreover, the degree of improvement is significant across all problem types. On TSP and ISSP, COMPASS reduces the optimality gap on the training distribution by a factor of 6.5 and 1.3, respectively. On CVRP, COMPASS is the only RI. method able to outperform the industrial solver LKH. Finally, COMPASS is also found to generalize well to larger problem instances unseen during training. COMPASS obtains the best solutions in all TSP and JSSP sets and is only outperformed by !Code, checkpoints and evaluation sets available at https h/tp///gttttttt cow wwwm///stadeppa//eeeeo compppsspcc/ppsssss//e/
7

---

0.0
5.
Pert. ratio (%)
-0.2
-0.2-
-1.3-
COMPASS (ours)
-044
Poppy
POMO
EAS
0.0
0.2
0.4
0.6
0.8
0.0
0.2 0.4
0.8
Mutation Power
Figure 3: Relative difference between COMPASS and baselines as function of mutation power. COMPASS outperforms the baselines all 18 evaluation sets. Most methods have decreasing performance ratio, showing that COMPASS generalizes better: its evolution strategy is able to find areas of its latent space that high- nigh-perffrming,
instances that are out-of-distribution
EAS on two instance sizes CVRP. Nevertheless, EAS is 50% slower and more computationally expensive as it requires updating an entire subset of its network's 's weights (see Appendix A), as opposed to simply navigating the 16-dimensional latent space of policies as done COMPASS.
The same benchmark is also reported with the "augmentation trick" in Table 2 for TSP and CVRP. This trick only be used for the routing problem and is not applicable for JSSP. Interestingly, COMPASS the only method that performs on par or better without the "augmentation trick", showing its ability adapt and find diversity in its latent space rather than through problem-specific trick. Other conclusions drawn above remain unchanged in this setting.
4.2 Robustness to generalization: solving mutated instances
To further study the generalization ability of our method, we consider the mutation operators intro- duced by Bossek al. (2019) to procedurally transform instances drawn from the training distribution. By progressively increasing the power of the applied mutations we construct new datasets that are increasingly far from the training distribution whilst not modifying the overall size of the problem.
We use 9 different mutation operators (explosion, implosion, cluster, rotation, linear projection, axis projection, expansion, compression and grid). One can find an illustration of the entire set of mutations along with their mathematical definition in Appendix C. Interestingly, it enables us to evaluate the methods on instances that look closer real-life situations. For instance, the operator that gathers nodes in cluster can mimic dense city surrounded by its nearby suburbs. In practice, each mutation operator parameterized by a factor that controls the probability of mutating each node of the instance referred to as mutation power this factor directly impacts the shift between the training distribution and the new distribution. We use 10 values, going from (no change) 0.9 (highly mutated instances).
Results We plot the relative performance of the baselines compared to COMPASS in Fig. 3. negative performance ratio indicates that a method does not provide as good of solution as COMPASS, and we observe that this is the case for all baseline methods, at all mutation strengths, on both TSP and CVRP. Moreover, COMPASS seen to generalize significantly better than the methods that only rely stochastic sampling for their search, namely POMO and Poppy. This validates intuition that adaptive policies are especially important for handling -itto---iittibttion data, where the optimal policy may be significantly different to that needed during pre-training. Even compared to EAS, which fine-tume tinettues the policy to the target problem instance, we find that COMPASS maintains significant performance gap across all mutation strengths. This result is particularly noteworthy as our approach only modifies 16 parameters (the conditioning vector sampled from our latent space), compared to EAS, which updates
than 1 parameters (the embeddings of the instance's nodes).
interesting to note that the relative generalization performance of COMPASS compared to EAS is stronger these mutated instances than the larger instances considered in Section 4.1. We

---

Overall Performance
Last Sample Performance
Distance from Optimal Tour Tou/Length Length
10"
10-1
commnoo lound
Search budget (%6
Figure 4: Evolution of the overall performance and last performance obtained by the methods during their search TSP150- averaged on 1000 instances. The right plot reports mean and standard deviations of the most recent shots tried by methods during the search. It illustrates how COMPASS efficiently explores its latent space to search for high-pes serh-performing solutions.
hypothesize that this is because EAS actively fine-tunes the embeddings of every location in given problem instance. Therefore, as the problem size increases, so does the number of free parameters to adapt the policy (albeit with commensurately increasing computational overhead). This suggests that further improvements to COMPASS could be possible by increasing the number of adapted parameters (i.e. the latent space dimension), however, we defer further investigation to future works.
4.3 Analysis of the search strategies
In this section, we analyze the structure of the latent space and the behavior of the search procedure both empirically and visually.
Figure details the performance of our considered meth- ods as function the overall search budget. The left panel reports the quality of the best solution found far (i.c. the cumulative performance), whereas the right plot reports the mean and standard deviations of the latest batch of solutions (i.e. the current performance) during the search process. From this, would highlight three main conclusions. (i) Adaptive methods (COMPASS, EAS) perform well as they able to improve the mean perfor- mance of their solution over time, in contrast to stochastic sampling methods (Poppy, POMO). This also highlights that the latent space of COMPASS has been able to di- (ii) Highly-focusee (low-
santergence
Figure 5: Contour plot of COMPASS's latent space, reflecting performance on problem instance. White crosses show the successive means of CMA-ES com- ponent during the search. The width of the path is proportional to the search's variance.
versify and can be exploited. variance) search does not always outperform stochastic exploration. Concretely, whilst EAS quickly adapts a pol- icy with better average performance than Poppy (right panel), the additional variance of Poppy's 's multiple diverse policies means it produces better overall solutions (left panel). (iii) COMPASS is able to combine both of the pre- viously discussed aspects for highly performant search procedure. By using an adaptive covariance mechanism as well as its multiple components to navigate several regions of the latent policy space, it focuses its search promising strategies (better average performance) whilst maintaining broad beam (higher variance).
To better understand how COMPASS's ' latent space is structured and explored, Fig. 5 presents the trajectory of single CMA-ES component during the search of a 2D latent space on a randomly chosen problem instance. We can first observe that even for specific problem instance, there are several high- nigh-performing areas interest which highlights the advantage of having multiple search components. Furthermore, it shows how the evolution strategy explores the space. The search variance is initially high to improve exploration until the search center moves into a higf-perg area, whereupon the variance is gradually decreased to better exploit these promising strategies. We

---

provide additional plots and explanation in Appendix E.2 for other problem instances, demonstrating the spread of the specialised areas depending on the problem instance.
Lastly, it is worth noting that the adaptation mechanism of COMPASS (CMA-ES search) comes with negligible time cost (e.g. three orders of magnitude smaller than the time needed for the environment rollout), which is a strength compared to the costly backpropagation-base updates performed in EAS. We provide additional time analysis in Appendix L.
Table 2: Results of COMPASS and the baseline algorithms with instance augmentation for (a) TSP and (b) CVRP. We also report COMPASS with no augmentation (no aug.).
(a) TSP
Training diste.
Generalization
n 1001
11 125
11 - 150
11 2000
Methevl
Chj
Clop
Time
Coop
Time
Dtj
Cee
Time
Otj
Clep
Time
CVAF-OpI
0.343%%
6D)
8.646
0. 0.739%
21H
9.482
1.45%
30H
SGRS
7.769
0.068%
9M
0.567
0.2259
RM
10.753
0.5195
14M
SCOS-EAS Lay
7.769
0.058%
311
9.359
0.174%
111
10.727
0.80%
311
POMD (sampling)
7.767
0.026%
211
8.591
0.128%
20M
9.376
0.321%
32M
10.915
2.14%
70M
Papoy 16
7.765
0.062%
2H
8.584
0.00%%
2061
9.351
0.141%
3IM
10.802
1.08%
7081
FAS
7.768
0.009%
7H
8.500
0.0825
66M
9.360
0.175%
138M
10.724
0.350
206M
COMPASS (ongg)
7.765
0.002%
2H
8.584
0.809%
2001
9.350
0.941%
SEM
10.723
0.337%
70M
COMPASS (no
7.765
0,002
211
8.586
0.036%
20M
9.354
0,083%
32M
10.724
0.348%
70M
(b) CVRP
Truining distr.
Generulization
100
125
150
200
Mothod
(bj.
Gisp
Time
Otj-
Time
Okj.
Clap
Time
Ubj.
Giup
Time
CVAE-OM
1.36%
11D
17.87
2,08%
36H
19:54
3.24 92
46H
SGBS
15.66
0.31%%
10M
19:43
1.085%
4MM
22.57
2.59%
YM
FAS--y
15,594
-0.36%
681
19,168
-8,27%
2H4
21.988
-0.85%
SH
POMO (sampling)
15.67
0,18%
411
17.56
0,33%
43M
19.43
1.08%%
111
23.24
5.64%
100M
Poppy 32
15.62
0.14%
411
17:49
-0.10%
42M
19:32
0.50%
111
22.94
4.27%
100M
15,62
-0.211
13H
40.117%
22.
0.73%
COMPASS
15,05
-0,00%
4H
0,09%
2.49%
100M
COMPASS ang.)
15,594
-0.36%
22.
2.10%
5 Conclusion
We present COMPASS, novel approach to solving CO problems using RL. Our approach is motivated by the observation that active search a key component to finding high-quality solutions to NP-hard problems. Finding one-shot solutions that near-optimal is believed to be impossible. Instead, COMPASS is trained to create a distribution of diverse and specialized policies, conditioned on structured latent space. This diversification is achieved by using an objective that specializes areas of the space on sub-distributions of problem instances. By navigating this latent space at inference time COMPASS is able find the most performant policy for a given instance. Empirical results show that COMPASS achieves state-of-the-ar performance on 9 out of standard benchmark tasks across three distinct CO problems, TSP, CVRP and JSSP, outperforming prior RL methods based on either stochastic sampling or fine-tuning. We extend the canonical evaluation sets with instances that are procedurally transformed using mutation operators introduced in prior work. This additional set of tasks enables us to assess the generalization ability of COMPASS. We show that instances, achieving superior performance in all 18 tasks considered. To better understand the benefits of our search procedure, we provide an empirical analysis of the latent space's ' structure, along with evidence of how it explored at inference time. We show that, despite having explicit regularization during training, the latent space exhibits clear regions of interest, and our search procedure able to explore this space using an evolution strategy to produce high-performing policies. Overall, COMPASS proves to be performant, robust, and versatile on many types of CO problems and is able to provide solutions quickly at a reasonable computational cost.
COMPASS particularly robust to out-of-distribus
Limitations and future work. The diversity of the policies contained in the latent space closely linked to the specialisation that can be obtained from the training distribution, and hence potentially limited. We would like to inspect whether broader range of policies could be obtained by using an additional unsupervised diversity reward, or by procedurally diversifying the distribution used. Another limitation of our method is the lack of structure in our latent space. Although we proved that it was enough to be successfully explored by an evolution strategy, we hypothesize that better defined space could be searched through faster. We would like to inspect the use of regularization terms during the training phase to achieve this.
10

---

Acknowledgements
Research supported with Cloud TPUs from Google's TPU Research Cloud (TRC). We thank anony- mous reviewers for comments and helpful discussions that helped improve the paper.
References
D. Applegate, R. Bixby, V. Chvatal, and W. Cook. Concorde TSP solver, 2006.
T. D. Barrett, W. R. Clements, N. Foerster, and A. I. Lvovsky. Exploratory combinatorial optimiza- tion with reinforcement learning. In In Proceedings of the 34th National Conference on Artificial Intelligence, AAAI, 2020.
I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.099/40 2016.
C. Bonnet, D. Luo, D. Byrne, S. Abramowitz, V. Coyette, Duckworth, D. Marelos-Blance N. Grin- sztajn, T. Kallomiatis, V. Le. O. Mahjoub, L. Midgley, S. Surana, C. Waters, and A. Laterre. Jumanji: a suite of diverse and challenging reinforcement learning environments in jax, 2023, URL https: / /gi thub. com/ instadeepai umanji.
J. Bossek, P. Kerschke, A. Neumann, M. Wagner, F. Neumann, and H. Trautmann. Evolving diverse tsp instances by means of novel and creative mutation operators. In Proceedings of the 15th ACM/SIGEVO Conference Foundations of Genetic Algorithms, FOGA '19, page 58-71, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450362542. doi: URL https: /tt..//ooioooa weeeii..rggiii org/10..//.. 1011112299994444 3340307.
10. 10.1145/3299944.3344
Bradbury, R. Frostig. P. Hawkins, M. Johnson, Leary, Maclaurin, Necula, Paszke, J. VanderPlas, S. Wanderman-Milne. and Q Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:/ /ttp://gttttt/ttt com/ mom//oogle/jaai
C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and Colton. survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1): 2012.
F. Chalumeau, R. Boige. B. Lim, V. Macé, M. Allard, A. Flajolet. A. Cully, and T. Pierrot. Neuroevo- lution is a competitive alternative to reinforcement learning for skill discovery. In International Conference Learning Representations, 2023a. URL 6BH1ZgyPOZY.
F. Chalumeau, B. Lim, R. Boige, M. Allard, L. Grillotti, M. Flageat, V. Macé, A. Flajolet, T. Pierrot, and Cully. Qdax: library for quality-diversity and population-based algorithms with hardware acceleration, 2023b.
X. Chen and Y. Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, 2019.
J. Choo, Y.-D. Kwon, J. Kim, J. Jac, A. Hottung, K. Tiemnyy and Y. Gwon. Simulation -urioon beam search for neural combinatorial optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2022. URL https: / /awxiv.iiiv.////ii//aaa//aaaaava org/ arg/aba/ aaaaabb22222 061900.
C. Contardo, C. Moreney, and L.-M. Rousseau. Balancing a dynamic public bike-sharing system, volume 4. 2012.
A. Cully. Multi-emitter map-elites: Improving quality, diversity and data efficiency with het- erogeneous sets of emitters. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '21, page 92, New York, NY, USA, 2021. Association for Com- puting Machinery. ISBN 9781450383509. doi: 22.14553444639.3459933 URL https: org/10. 10. 1145/3449639 3459326.
H. Dai, F. B. Khalil, Y. Zhang, Dilkina, and I.. Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, 2017.

---

P. R. de O. da Costa, J. Rhuggenaath, Y. Zhang, and A. Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, 2020.
M. Deudon, P. Cournut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau. Learning heuristics for the tsp by policy gradient. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 170-181. Springer International Publishing, 2018.
Q. Du, V. Faber, and M. Gunzburger. Centroidal voronoi tessellations: Applications and algorithms. SIAM Review, 41 1999. doi: 10. 10.1137/503661444992266 URL https: //doi. org/10. 1137 011173/0000114459932222222
B. Eysenbach, A. Gupta, J. Ibarz, and Levine. Diversity is all you need: Learning skills without reward function. In International Conference on Learning Representations, 2019.
M. C. Fontaine, J. Togelius, S. Nikolaidis, and A. K. Hoover. Covariance matrix adaptation for the rapid illumination behavior space. Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO '20, page 94-102, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450371288 doi: 10.1145/3379930.339022 URL https://doi.. orggioorg/00 10. / 3390232.
A. Froger, M. Gendreau, J. E. Mendoza, Éric Pinson, and L.-M. Rousseau. Maintenance scheduling in the electricity industry: A literature review. European Journal of Operational Research, 251 (3):695-706, 2016. ISSN 0377-2217.
045.. URL doi: httta////arrrte//////////1111100
www.seiwwwweeeeicccc.... httgss//www.siiimcciiieee.c wwt.///ciin//arrrreeeeeooo/o//ee
N. Grinsztajn, D. Furelos-Blanco, and T. D. Barrett. Population-based reinforcement learning for
combinatorial optimization. arXiv preprint arXiv:2210.03475, 2022.
N. Hansen and A. Ostermeier. Completely derandomized self-adaptatiion in evolution strategies. Evolutionary Computation, 92):159-195, 2001. doi: 10.1162/10633556115000933333
K. Helsgaun. An extension of the lin Beemighannhelsgane tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde University, Tech. Rep., 2017.
J. J. Hopfield and W. D. Tank. "neural" computation of decisions in optimization problems. Biological cybernetics, 52(3):441-52, 1985.
A. Hottung and K. Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. In 24th European Conference Artificial Intelligence (ECAI 2020), 2020.
A. Hottung, B. Bhandari, and K. Tiemey. Learning latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2021.
A. Hottung, Y.-D. Kwon, and K. Tierney. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
M. Kim, J. Park, and J. Kim. Learning collaborative policies to solve np-hard routing problems. In Advances in Neural Information Processing Systems, 2021.
M. Kim, J. Park, and J. Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimiza- tion. In Advances in Neural Information Processing Systems, 2022. doi: 10.48550/arXiv.2205. 13209.
W. Kool, H. van Hoof, and M. Welling, Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Y.DD. Kwon, B. K. Jinho Choo, Y. G. Iljoo Yoon, and S. Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In Advances Neural Information Processing Systems, 2020.
A. Laterre, Y. Fu, M. K. Jabri, A.-S. Cohen, D. Kas, K. Hajjar, T. S. Dahl, A. Kerkeni, and K. Beguir. Ranked reward: Enabling self-play reinforcement learning for combinatorial optimization. arXiv preprint arXiv:1807.01677 2018.
12

---

B. Lim, M. Allard, L. Grillotti, and A. Cully. Accelerated quality-diversit for robotics through massive parallelism. arXiv preprint arXiv:2202.01255, 2022.
Y. Ma, J. Li. Z. Cao, W. Song, L. Zhang, Z. Chen, and Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neural Information Processing Systems, volume 34, pages 1099-11107, 2021.
N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134:105400, 2021. ISSN 0305- 0548. doi: https://doi.org// wrtp://oo//...1///.oooooooooooo 105400. URL wttp://wwww.cciieeeereeettttt com/science wwwaaceetiiiiiiieeeee ptt.://ccc....///333333330110000
L. Perron and V. Furnon. OR-Tools, 2019. URL https://developersggoooo com/
optimization/.
A. Sharma, S. Gu, S. Levine, V. Kumar, and K. Hausman. Dynamics-aware unsupervised discovery of skills. arXiv preprint arXiv:990700/65/ 2019.
V. Steinbiss, B.-H. Tran, and Ney. Improvements in beam search. In Third international conference spoken language processing, 1994.
A. Vaswani, N. Shazeer, N. Parmar, Uszkoreit, L. Jones, Gomez, L. Kaiser, and I. Polosukhin. Attention all you need. In Advances in Neural Information Processing Systems, 2017.
O. Vinyals, M. Fortunato, and N. Jaitly, Pointer networks. In Advances in Neural Information Processing Systems, 2015.
Y. Wu, W. Song, Cao, Zhang, and A. Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 33())505775506, 2022.
L. Xin, W. Song. Z. Cao, and J. Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the 35th National Conference on Artificial Intelligence, AAAI, 2021.
C. Zhang, W. Song. Z. Cao, Zhang, P. S. Tan, and C. Xu. Learning dispatch for job shop scheduling via deep reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
13


Reviews:
[{"review_id": "ZEUhLQZCml", "reviewer": "Reviewer_YBD4", "summary": "The paper proposes a neural combinatorial optimization approach that allows for an extensive search for high-quality solutions. The approach uses reinforcement learning to train a network to construct solutions for the traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), and job shop scheduling problem (JSSP). During training, the network is trained to parameterize a diverse set of policies that are conditioned on a continuous latent space. At test time, a guided search is performed using Covariance Matrix Adaptation (CMA-ES) to find regions in the continuous latent space that are associated with policies leading to high-quality solutions. The experiments indicate that the proposed method provides a competitive performance and is able to generalize well to instances that are different from those seen during training.", "questions": "", "limitations": "- The paper does not discuss limitations of the proposed method.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The results show that the method offers a very good performance on all considered problems.\n- The paper addresses an important problem (designing a neural combinatorial optimization approach that is able to perform an extensive search).\n- The authors perform some interesting generalization experiments that go beyond changing only the instance size and also considers other shifts in the distribution. \n- The authors will make the code of their method publicly available.\n- Overall, the paper is well written and clearly organized.", "weaknesses": "- The proposed method is very similar to the method from [Hottung et al.] which also trains a neural network conditioned on a continuous latent space to construct diverse solutions to routing problems. At test time, both methods search the continuous latent space using continuous optimization methods (in this work CMA-ES, in Hottung et al. differential evolution.) The authors should make this clear in the paper and discuss the differences between the methods.\n- In general, the paper omits discussing most of the existing works on learning extensive search methods (or improvement methods) for combinatorial optimization problems. Instead the authors conclude that “[..] the field has reached a point where methods [...] can hardly make significant improvements [over quickly generated solutions when] given a budget for additional computation.” (page 2) In fact, many approaches have been proposed that aim to exploit bigger computation budgets and that perform an extensive, guided search:\n   - Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems 32, 2019.\n   - André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. European Conference on Artificial Intelligence, pages 443–450, 2020.\n   - Kim, Minsu, and Jinkyoo Park. \"Learning collaborative policies to solve NP-hard routing problems.\" Advances in Neural Information Processing Systems 34 (2021): 10418-10430.\n   - Ma, Yining, et al. \"Learning to iteratively solve routing problems with dual-aspect collaborative transformer.\" Advances in Neural Information Processing Systems 34 (2021): 11096-11107.\n\n- The reported performance of the baseline approaches is significantly worse than in their original works.\n   - The validity of the experimental results is limited by the fact that the authors remove a core component from the considered baseline approaches. More precisely, the authors do not use instance augmentation (which considers 8 different augmentations of each test instance during the search). Using augmentations of an instance is an established way of increasing the exploration during the search, because neural network based construction methods tend to generate different solutions for each augmented version of an instance). While it can be argued that an augmentation mechanism is a “domain-specific trick” it also can be considered unfair to remove a component from a baseline approach that encourages exploration without replacing it with a different component that increases exploration. Most methods will perform worse if  a component that the developers considered as given when designing the method (even if it can be easily replaced by something else) is removed. Hence, I suggest that the authors also report results for the baselines with augmentation.\n   - The authors reimplement the baseline approaches even though their code is publicly available. This has some pros and cons. On the plus side, implementing all approaches within the same code base allows a fair comparison of the runtime unaffected by implementation tricks or differences in the speed of the used framework. However, (to my surprise) the authors do not report any runtimes in the main paper. On the negative side, there is a risk that the implementation does not work as well as the original approach due small mistakes/misunderstandings. Currently, it is not possible to evaluate if the implementation of the authors matches the performance of the original code base because the authors do not report results with the augmentation mechanism being enabled. Hence, I again suggest that the authors also report results for the baselines with augmentation to demonstrate that their reimplementation is correct (in that case having a unified code base for all approaches could even be considered a strength of the paper).\n- The authors should make it more clear if they used identical test instances to earlier work or if they generated new test instances (I hope the former, because generating new test instances makes a comparison to earlier works unnecessarily difficult).\n\n[Hottung et al.] Hottung, André, Bhanu Bhandari, and Kevin Tierney. \"Learning a latent search space for routing problems using variational autoencoders.\" International Conference on Learning Representations. 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and positive feedback. We will update the paper accordingly and have added additional experiments to help address their concerns.\n\n> W1: The proposed method is very similar to CVAE-Opt [1]. The authors should make it clear in the paper and discuss the differences.\n\nWe agree that the work of [1], CVAE-Opt, merits discussion, however, there are significant differences both algorithmically and in terms of empirical performance between this work and COMPASS. Specifically, whilst [1] also trains a neural network conditioned on a continuous latent space and explores it at inference time:\n- Our method is entirely trained with reinforcement learning and hence, unlike [1],  does not require any direct supervision from pre-solved instances and is hence amenable to problems where no good prior solver is available.\n- CVAE-Opt has to additionally train a recurrent encoder of (instance, solution) pairs.  By contrast, COMPASS considers the latent space to encode a distribution of complementary policies and can be easily applied to pre-trained models (e.g. POMO).\n- Our method significantly outperforms the work of [1] whilst also having a significantly shorter runtime, as reported in Table 1 of the pdf file attached (will be added to Appendix A.1.1).\n\nWhilst our initial intention was to focus our Related Work section on RL construction methods, we will update it to cover a larger set of methods and ensure that [1] is discussed in any revised manuscript. \n\n> W2: The paper omits discussing most of the existing works on learning extensive search methods (or improvement methods). [And statement L. 41/42 is misleading].\n\nThe sentence (L. 41/42) was referring to RL construction methods, however we accept that this was not sufficiently clear and will update the phrasing to make this explicit. Additionally, we will update our Related Work section to inform readers that there also exists a literature on improvement methods which propose approaches to exploit increased computation time. Finally, we will present the most relevant papers on improvement methods in a new section of the Appendix.\n\nSince the literature on construction methods is both extensive and more directly related to our work, we believe it is important to ensure this remains the key focus of the main manuscript (similarly to [3]) with extended context provided in the Appendices.\n\n> W3: The validity of the experimental results is limited by the fact that the authors (...) do not use instance augmentation. I (...) suggest also reporting results for the baselines with augmentation to demonstrate that their re-implementation is correct.\n\nWe agree with the reviewer that reporting the results with problem augmentation is an important step to validate our implementations, and hence to strengthen our experimental results. Consequently, we have re-run the entire benchmark with instance augmentation.  The results will be added to the Appendix and are reported in the file attached to our rebuttal. Concerning the runtime, they were already reported in Table 2 of Appendix A.1.1 but we will add them to Table 1 (main paper).\n\nWith regards to the correctness of our implementations; the reported POMO results are run in-house and match, or outperform, the published results in [2] where available.  We also independently verified that our re-implementation of EAS on TSP100 and CVRP100 with augmentations is consistent with the published results.\n\nWe think that it is fair to run the benchmark without instance augmentation. As mentioned by the reviewer, those are domain specific tricks that cannot always be used (e.g. JSSP). It is hence crucial to develop approaches that do not rely on those for exploration. In addition, it is important to mention that the baselines still benefit from a strong exploration in our benchmark, as they all use the multiple starting positions introduced in [2]. \n\nFinally, we note the use of augmentations makes fair comparison to methods designed for inference-time search challenging. In the literature, 8 augmentations are typically used for each problem instance following the protocol of [2]; however this choice is arbitrary and in practice any number could be used. Larger numbers allow more deterministic samples from a specific policy, but therefore also leave less of the inference budget for subsequent steps with updated policies when using adaptive methods such as EAS and COMPASS. Indeed, in these cases the optimal number of augmentations would have to be tuned as an additional hyper-parameter of the search.\n\nThat being said, we agree that for continuity with previous work, it is valuable to run and report those results, which we did for the rebuttal. Whilst the overall ranking of different methods is nearly always unchanged, we can still extract interesting observations from those results. In particular (i) COMPASS remains state-of-the-art on all instance sizes for TSP (ii) on CVRP, COMPASS makes better use of its budget by exploring its latent space rather than relying on the instance augmentation. In particular, COMPASS with no augmentation outperforms all other methods with augmentation on CVRP 100.\n\n> W4: The authors should make it clearer if they used identical test instances to earlier work.\n\nWe reuse identical test instances as the methods we compare to. We will update the paper to make it clearer. \n\n> The paper does not discuss limitations.\n\nWe discuss limitations of our method in the Appendix (A.14). We nevertheless agree that limitations should be mentioned in the main paper: we will add a paragraph in the conclusion.\n\n---\n[1] Hottung et al., Learning a latent search space for routing problems using variational autoencoders. ICLR (2020).\n\n[2] Kwon et al., Pomo: Policy optimization with multiple optima for reinforcement learning. Neurips (2020).\n\n[3] Kim et al., Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization. Neurips (2022)."}, {"review_id": "xWFh4UgRC8", "reviewer": "Reviewer_Qr8r", "summary": "This paper proposes COMPASS, an RL-based training framework to learn a diversified neural solver for combinatorial optimization problems. This framework trains a conditioned neural network conditioned on a prior vector sampled from a fixed distribution. During the training phase, multiple priors are sampled, and only the parameters corresponding to the best prior are updated. During the inference phase, the evolution algorithm is employed to find the best prior for the current instance.\n\nThe authors test its method on TSP, CVRP, and JSSP. The experiment design is solid, and the results are promising. \n\n", "questions": "1. Like mentioned in weakness (2), I am wondering what's the results of comparing COMPASS with COMPASS base neural solver + beam search/heuristic search. The traditional search can use fewer resources. \n\n2. For the deep learning-based baselines, comparing time is insignificant. But I am wondering about the time cost of COMPASS. This can give me more confidence to evaluate how efficient COMPASS is. And to evaluate whether it can be used for real-world problems.\n\n3. To my knowledge, TSP 100 and TSP 200 do not makes too much difference for a neural solver. I am wondering what's the results of testing on TSP 1000. ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The resources, e.g., memory and time, used in the inference time are shorter than the current SOTA from its low-dimensional prior.\n\n2. The learned conditional neural solver has the potential to generalize to the out-of-training distribution instances. That is also somehow verified from the section 4.2 experiments.\n\n", "weaknesses": "1. One key challenge in the RL for CO area is how to train/generalize a model to the real big cases, e.g., TSP1000/10000. This framework is designed to improve upon another neural solver. However, it cannot solve the real big cases. \n\n2. In the inference time, the priors are sampled and selected using the evolution algorithm. This is somehow like a search-related method. It is not clearly verified \"the improvement comes from a good conditional neural solver or the strong evolution algorithm\". ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback and hope that our answers and additional experiments will clarify any concerns.\n\n> W1: Key challenge in RL for CO is to train/generalize a model to big cases, e.g. TSP1000/10000. This framework is designed to improve upon another neural solver [but] cannot solve big cases.\n\nWe agree with the reviewer that scaling models to larger instances is an important challenge. However, whilst this is not a key focus of our work, we nonetheless believe that our method can contribute towards this goal. Concretely, two crucial aspects for tackling larger instance sizes are generalization and scalable architecture. Our method is SOTA for generalization (see Fig. 3), with scalable latent space adaptation that is independent of instance size). Furthermore, our method is architecture-agnostic.  Although we do not innovate on architecture, we can benefit from any new scalable architecture; e.g. nothing prevents us from using COMPASS on DIMES [1] and hence solve much larger instances, although this is beyond the scope of this work.\n\n> W2: It is not clearly verified whether the improvement [at inference time] comes from a good conditional neural solver or the strong evolution algorithm.\n\nOur experimental results provide evidence that both aspects – (1) a well-trained conditional neural solver and (2) an efficient search algorithm – are critical for strong performance. It can be seen in both the reported results in the paper and the attached pdf with additional experiments. We agree this is a crucial point and will therefore update the manuscript accordingly.\n\n**Previous results** Point (1) is illustrated by Fig. 4 (main) which shows high-performing regions for a given instance. Point (2) is demonstrated by Fig 9 (appendix) which shows the principled search method significantly outperforms random search. Additionally, we see that the random search outperforms POMO and Poppy, confirming that the latent space “contains” high-performing and diverse policies.\n\n**New Exp. 1** This is further illustrated in Fig. 1 (attached pdf) which compares two COMPASS models (fully- vs. under-trained) solving TSP150 instances with two search methods (CMA-ES and uniform sampling). The results demonstrate that:\n- Both search methods for fully trained model outperform those for under-trained model, showing the importance of our training procedure.\n- Uniform search on the fully-trained solver outperforms CMA-ES search on the under-trained model, showing that the search alone is not sufficient.\n\n**New Exp. 2** Fig. 2 (attached pdf) presents the evolution of the latent space during training on a TSP150 instance. It can be seen that initially the space is uniform (no specialized regions exist). However, as training progresses, high-performing regions emerge (shown in red) which indicates specialization of policies within the latent space, and we also see the improved performance of the best conditioned policy.\n\n> Q1: What are the results of comparing COMPASS with COMPASS base neural solver + beam search/heuristic search.\n\nThis can be approximated by comparing with SGBS, a heuristic approach to improve the performance of POMO [2]. A naive application of this heuristic on COMPASS (sampling a random POMO policy with no latent space search) is equivalent to POMO+SGBS. We report the results of POMO+SGBS in Table 1 (attached pdf) and show that COMPASS outperforms POMO+SGBS on the whole benchmark. This validates that it is worth searching for a good latent condition with the budget rather than fixing a random policy and using a beam search. Nevertheless, there may be a trade-off between search in latent space and heuristic solution search, which we will mention in the updated manuscript.\n\n> Q2: What is the time cost of COMPASS?\n\nTime performance is reported in Table 2 (appendix), but we will update Table 1 (main) with the times. These results show that (i) COMPASS is as fast as POMO and POPPY (time cost of CMA-ES search is insignificant) (ii) COMPASS is significantly faster than EAS, e.g. 4x faster on CVRP 200.\n\nThe adaptation mechanism of COMPASS comes with negligible time cost. We ran additional experiments to time the solution construction process of COMPASS. Those are reported in Table 2 of the attached rebuttal file and will be added to the Appendix. In a complete rollout of TSP100, the CMA-ES sampling and update takes 0.28 milliseconds, which is three orders of magnitude smaller than the time of the 99 decoding steps (298 ms).\n\n> Q3: To my knowledge, TSP100 and TSP200 do not make too much difference for a neural solver. I am wondering what the results of testing on TSP 1000 are.\n\nWe believe that the difference between TSP100 and TSP200 is important, especially when considering generalization to larger instances as all checkpoints are trained on TSP100. Additionally, TSP 125, 150 and 200 are commonly used benchmark sets from the literature [3-5] and therefore valuable to report for consistency and to enable direct comparison.\n\nWe agree scaling to larger instances is a prescient challenge which we discuss in the context of COMPASS in our response to W1.  As an initial examination on TSP1000, we run COMPASS, Poppy and POMO on the instances from [1], taking 7H each. COMPASS outperforms them by a significant margin (29.28 vs. 39.03 & 50.02). EAS-Emb is intractable on TSP1000, but EAS-Tab is reported in [1] and is largely outperformed as well (49.56 in 63.45H).\n\n---\n\n[1] Qiu et al., DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. NeurIPS (2022).\n\n[2] Choo et al., Simulation-guided beam search for neural combinatorial optimization. NeurIPS (2022).\n\n[3] Grinsztajn et al., Population-based reinforcement learning for combinatorial optimization. (2022).\n\n[4] Hottung et al., Efficient active search for combinatorial optimization problems. ICLR (2022).\n\n[5] Kwon et al., Pomo: Policy optimization with multiple optima for reinforcement learning. NeurIPS (2020).\n"}, {"review_id": "XhEDLQbRMW", "reviewer": "Reviewer_ubWG", "summary": "Building upon a pre-trained neural constructive model (such as POMO), this paper proposes COMPASS, which introduces the idea of learning a continuous latent search space to fine-tune the pre-trained POMO model parameter. The latent space allows for the sampling of a vector, which the pre-trained POMO model uses as a conditional vector to generate its own parameters. After training such latent space, continuous optimization algorithms (such as CAM-ES) can be utilized to search this space, in order to yield the most performant POMO model parameters for each test instance during inference. This allows for per-instance search during inference, while avoiding the need to retrain the deep model for each new test data (as is the case with active search in EAS). Experiments on benchmarks verify that COMPASS outperforms the state-of-the-art baselines.", "questions": "1. Does the run time include the time taken for CAM-ES? If so, what is the ratio of CAM-ES time to the total time?\n2. In your comparison table, were all results obtained on your server? If so, could you provide the CPU/GPU model type of your serverfor readers to fully understand the efficiency?\n3. How long does it take to train COMPASS and how many computational cost?\n4. It would be interesting to investigate if COMPASS could enhance neural improvement heuristics like LIH, thereby yielding variable neighborhood search.", "limitations": "The revised paper should mention more limitations and future works.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The concept of learning a latent search space for fine-tuning parameters of an NCO model is novel and could potentially impact the NCO community positively. However, it is important to acknowledge that the idea of learning a latent search space followed by using continuous optimizer to search within the space is not new, as evidenced by the CVAE-Opt method (ICLR’21).\n- The authors conducted comprehensive experiments, supported by detailed tables, figures, and useful visualizations.\n- COMPASS achieves state-of-the-art performance on benchmark TSP-100 and CVRP-100 instances.\n", "weaknesses": "- Although the authors provided reasons, I still think it would be useful to benchmark COMPASS against POMO and EAS equipped with data augmentation, to gain a complete understanding of COMPASS's advantages. That is to say, all baseline should be at their best settings. Furthermore, the recent method SGBS (simulation guided beam search, NeurIPS’22) is also overlooked.\n- The method by which POMO is conditioned on the vector sampled from the latent space is unclear. Specifically, given a pre-trained NCO model, how should the user determine which parameters to condition on in practice?\n- The literature review lacks comprehensiveness, missing important works like CVAE-Opt, SGBS, and other recent works.\n- COMPASS's generalization to larger sizes (CVRP-200) appears less efficient than EAS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments.\n\n> W1: ... it would be useful to benchmark COMPASS against POMO and EAS with data augmentation. Furthermore, SGBS … is overlooked.\n\nWe are happy to provide additional benchmarking to allow comparison to published results and validate our implementations. These are provided in the attached pdf (Table 1) and will be added to the Appendices of a revised manuscript. We believe not using augmentations for the results in the main text remains suitable, as discussed below.\n\n**Benchmarking: augmentations and SGBS** The key messages are unchanged from the previously reported results.\n- COMPASS outperforms all baselines with instance augmentation for all TSP instance sizes.\n- COMPASS is the leading method for in-distribution CVRP, with EAS providing stronger adaptation on larger instances (we note the adaption of EAS does not come without tradeoffs as discussed in our response to W4).\n- We also add SGBS [1] and CVAE-Opt [2]. COMPASS significantly outperforms both methods for all instance sizes of TSP and CVRP.\n\n**Augmentation-free results** We reaffirm the motivation behind running COMPASS and the baselines without instance augmentation.\n- Instance augmentation is a domain-specific trick which cannot be used for all problems (e.g. JSSP, Knapsack).\n- Baseline methods still benefit from a strong exploration as they use multiple starting points [3] and a substantial search budget.\n- Using augmentations complicates fair comparisons with inference-time search methods. Typically, 8 augmentations are used based on [3]. However, this number is arbitrary. More augmentations increase the number of samples from a specific policy, limiting the number of  adaptive steps for methods like EAS and COMPASS. \n\n> W2: How is POMO conditioned on the latent space… how to determine which parameters to condition on in practice?\n\nThe decoder is conditioned on a vector sampled from a 16-dim latent space and is fully described in Appendix A.5. Specifically, the latent vector is concatenated with the key, query, and value inputs of the multi-head attention. For clarity we will add a brief description in the Methods section with reference to A.5 for further details.\n\nWhilst COMPASS is agnostic to the network architecture, we did not extensively explore alternative conditioning methods and leave this to future work.\n\n> W3: The literature review [is] missing important works like CVAE-Opt, SGBS and other recent works.\n\nOur literature review focused on RL construction methods, but we agree that a broader review can benefit future readers. Therefore, we will include discussions of CVAE-Opt and RL improvement methods. SGBS is already included in the Related Work (L. 90-91). We also provide CVAE-Opt and SGBS as additional baselines in the attached pdf (Table 1), which will also be included in the revised manuscript.\n\n> W4: COMPASS's generalization to larger sizes (CVRP-200) appears less efficient than EAS.\n\nEAS does adapt to the largest CVRP instances more effectively, however to achieve this it (1) adapts orders of magnitude more parameters (e.g. for CVRP200, EAS adapts 200*128=25.6k parameters compared to the 16-dim latent vector of COMPASS), (2) requires computationally expensive test-time training. Increasing the capacity of COMPASS (e.g. a larger latent space) can be explored in future work and we note that COMPASS and EAS are not mutually exclusive, and so could be combined.\n\nDespite these points, COMPASS outperforms EAS on in-distribution CVRP, all considered TSP and JSSP instance sizes and all the 18 generalization tasks (where instances are procedurally transformed to be out-of-distribution).\n\n> Q1: Does the run time include the time taken for CMA-ES? What is the ratio of CMA-ES time to the total time?\n\nRun times include CMA-ES steps, though this adaption makes a negligible contribution to the overall timings (in contrast explicit fine-tuning methods, e.g EAS). Details are provided in Table 2 of the attached pdf and will be included in a revised Appendix.\n\n> Q2: In Table 1, were all results obtained on your server? Could you provide the CPU/GPU model type…?\n\nCOMPASS’ results and all baselines (POMO, POPPY and EAS) were computed by us using a v3-8 TPU. We used previously released checkpoints for these models to ensure consistency. We will update the main paper to include these details.\n\n> Q3: How long does it take to train COMPASS and how much computational cost?\n\nThe final COMPASS models are trained until convergence, for each problem the training time and environment steps are: 4.5 days (110M steps) for TSP, 5.5 days (76.5M steps) for CVRP and 4.5 days (4.2M steps) for JSSP. These details will be added to the revised manuscript.\n\n> Q4: It would be interesting to investigate if COMPASS could enhance neural improvement heuristics like LIH, thereby yielding variable neighborhood search.\n\nWe agree this is a promising future direction. In LIH, finding a diverse set of candidate solutions is also desired (see section V.C of [4]). As COMPASS is applicable to any pretrained model, instead of using the same policy stochastically several times (multi-run), or a selection of, likely similar, policies found during training (multi-policy), LIH could use COMPASS to promote diversity and subsequently improve performance.\n\n> The revised paper should mention more limitations and future works.\n\nAppendix A.14 discusses limitations and future work, however we accept this should be presented more prominently. In the revised text we will update the conclusion accordingly.\n\n---\n\n[1] Choo et al., Simulation-guided beam search for neural combinatorial optimization. NeurIPS (2022).\n\n[2] Hottung et al., Learning a latent search space for routing problems using variational autoencoders. ICLR (2020).\n\n[3] Kwon et al., Pomo: Policy optimization with multiple optima for reinforcement learning. NeurIPS (2020).\n\n[4] Wu et al., Learning Improvement Heuristics for Solving Routing Problems. IEEE (2022)."}, {"review_id": "vI0VSPVb5P", "reviewer": "Reviewer_GNoz", "summary": "This paper presents an interesting CO agent model that conditions policy by latent vectors and finds latent vectors through CMA-ES.\nIn addition, considering latent vector in the learning process, this paper presents a training method that induces the agent to be specialized for various instances.", "questions": "1. Could you elaborate more on the conditioned decoder? \n\n2. Since Equation (1) lacks a baseline, the learning stability is likely to be poorer compared to methods such as POMO and Puppy, which use a baseline in gradient calculation. Is there a particular reason for not using a baseline?\n", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The idea of ​​using latent vectors to condition the policy and updating latent vectors via CMA-ES during inference is novel.   \n\n2. The training method with this inference method in mind is also interesting.", "weaknesses": "1. Inference time is not included in Table1. Since COMPASS is a method of continuously finding a better solution during inference, it is crucial to include the inference time in the experimental results.   \n\n2. It is difficult to view the experimental results of COMPASS as state-of-the-art results considering EAS (Hottung et al., 2022), SGBS+EAS (Choo et al., 2022) and DPDP [1] in CVRP experiments.\n\n3. Overall, the description of the model structure, training method, and inference method lacks details.  \n\n\n***\n\n[1] Kool, Wouter, et al. \"Deep policy dynamic programming for vehicle routing problems.\" Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and positive feedback. We have updated the paper accordingly and hope our answers further clarify the aspects of the COMPASS framework and the training procedure. \n\n> W1: Inference time is not included in Table1. Since COMPASS is a method of continuously finding a better solution during inference, it is crucial to include the inference time in the experimental results.\n\nWe agree that this is an important context and will therefore include the inference times of all methods and CO problems (previously reported in the Appendix Table 2) to Table 1 of the main text.\n\n> W2: It is difficult to view COMPASS as SOTA considering EAS (Hottung et al., 2022), SGBS+EAS (Choo et al., 2022) and DPDP (Kool et al., 2022) in CVRP experiments.\n\nWhilst EAS and SGBS+EAS do provide stronger adaptation to larger CVRP instances, we emphasize that this performance comes also with practical trade-offs and that the totality of all experiments strongly supports COMPASS as the leading method.\n\nConcretely,  EAS has orders of magnitude more adaptable parameters that must be re-trained (with non-negligible overhead and scalability challenges) on every considered instance - we refer the reviewer to our response to point W4 of reviewer ubWG for a more detailed discussion of the relative trade-offs of EAS.\n\nMoreover, on 9 out of 11 standard benchmarking tasks and all 18 generalization tasks, COMPASS outperforms the prior state-of-the-art approaches. With respect to the specific methods raised by the reviewer; (i) COMPASS outperforms the results presented by DPDP [1] on both TSP100 and CVRP100, (ii) COMPASS could, in principle, be combined with SGBS and EAS to further improve performance as the distribution of specialized policies encoded in the latent-space could still be used in conjunction with beam-search or fine-tuning at inference time.\n\n> W3: Overall, the description of the model structure, training method, and inference method lacks details.\n\nDetails on these points are provided in the Appendices of the original submission, however we accept that they are important context and will ensure each is either moved into, or explicitly referenced in, our next revision of the main text. Specifically;\n- The model architecture for TSP and CVRP is fully described in Appendix A.5.  The JSSP model is described in Appendix A.12.\n- The training procedure is described in the Methods section of the main paper, which refers to Appendix A.7 for further details including pseudo-code for, and step-by-step details of, the algorithm.\n- The inference procedure is described in the Methods section of the main paper, which references Appendix A.8 for additional details and discussion of alternatives inference-time search protocols.\n\n> Q1: Could you elaborate more on the conditioned decoder?\n\nThe decoder is conditioned on a vector sampled from a 16-dimension latent space. This latent vector is concatenated with the key, query, and value inputs of the multi-head attention decoder module. This conditioning allows us to create distinct policies while processing the same observation from the environment. Each latent vector corresponds to a unique policy, and thus, sampling the latent space to obtain vectors that our model can condition upon gives us an infinite set of policies.\n\nThe conditioned decoder is described in Appendix A.5.  As discussed in our response to W3, we will ensure that the updated manuscript contains a brief description regarding the conditioned decoder in the methods section along with an explicit reference to Appendix A.5 for further details.\n\n> Q2: Since Equation (1) lacks a baseline, the learning stability is likely to be poorer compared to methods such as POMO and Poppy, which use a baseline in gradient calculation. \n\nWe thank the reviewer for highlighting this oversight; in fact COMPASS does use a baseline in the gradient calculation; specifically it is the same baseline used in POMO and Poppy. We will updated Equation (1), which defines the gradient of the COMPASS objective, to the following:\n\n$$ \\\\nabla\\_\\\\theta J\\_{\\\\text{compass}} = \\\\mathbb{E}\\_{\\\\rho \\\\sim \\\\mathcal{D}} \\\\mathbb{E}\\_{z\\_1, ..., z\\_N \\\\sim \\\\mathcal{P}\\_z} \\\\mathbb{E}\\_{\\\\tau\\_i \\\\sim \\\\pi\\_\\\\theta(\\\\cdot |z\\_i)} [\\\\nabla\\_\\\\theta \\\\log \\\\pi\\_\\\\theta(\\\\tau\\_{i^\\\\star} | z\\_{i^\\\\star})R\\_{i^\\\\star} - \\\\mathcal{B}] $$\n\nwhere B is the baseline.\n\n---\n\n[1] Kool et al. \"Deep policy dynamic programming for vehicle routing problems.\" CPAIOR (2022)."}]

Author rebuttal:
We thank the reviewers for their positive comments, feedback and suggestions. In particular we are pleased to see the contributions of our work; both methodological and strong empirical performance, highlighted.

We respond to each question and concern in detail for each reviewer independently. However, in general, the recurring themes were requests for (1) extended results and discussions of additional solving methods; either using instance augmentation common for TSP and CVRP (Qr8r, ubWG) or additional models such as CVAE-Opt, SGBS, DPDP (YBD4, ubWG, ubWG), and (2) clarification of technical details and timings (YBD4, Qr8r, ubWG, GNoz).

We have provided additional results relating to point (1) in the attached pdf, namely Table 1.  We find that the overall messages of the paper, such as COMPASS remaining the most performant RL method is unchanged. In particular, COMPASS significantly outperforms the additional baselines requested.  For point (2) we have provided all additional information requested; with supporting figures in the attached pdf, clarifying our manuscript where details were missing, and including additional references to the relevant section of the Appendices.

We thank the reviewers for raising these points as the additional results further strengthen our contributions.  We believe that all raised points have been addressed and would be happy to discuss any remaining concerns that the reviewers may have. 


Meta-review: The paper proposes a neural combinatorial optimization approach to produce high-quality solutions. The approach employs reinforcement learning to train a network to parameterize a diverse set of policies that are conditioned on a continuous latent space. For a new testing problem, guided search is performed using CMA-ES to find regions in the latent space that are associated with policies leading to high-quality solutions. Experiments show good results on benchmark combinatorial optimization problems.

Overall, reviewers' were positive about the paper and author rebuttal addressed their questions and concerns. 

I recommend accepting the paper and strongly encourage the authors' to incorporate reviewers' comments and rebuttal discussion into the final paper.
Decision: Accept (poster)