Self-Improvement for Neural Combinatorial Optimization: Sample Without Replacement, but Improvement
Authors: Jonathan Pirnay
Dominik G. Grimm
Venue: Accepted by TMLR ()

Abstract: Current methods for end-to-end constructive neural combinatorial optimization usually train a policy using behavior cloning from expert solutions or policy gradient methods from reinforcement learning. While behavior cloning is straightforward, it requires expensive expert solutions, and policy gradient methods are often computationally demanding and complex to fine-tune. In this work, we bridge the two and simplify the training process by sampling multiple solutions for random instances using the current model in each epoch and then selecting the best solution as an expert trajectory for supervised imitation learning. To achieve progressively improving solutions with minimal sampling, we introduce a method that combines round-wise Stochastic Beam Search with an update strategy derived from a provable policy improvement. This strategy refines the policy between rounds by utilizing the advantage of the sampled sequences with almost no computational overhead. We evaluate our approach on the Traveling Salesman Problem and the Capacitated Vehicle Routing Problem. The models trained with our method achieve comparable performance and generalization to those trained with expert data. Additionally, we apply our method to the Job Shop Scheduling Problem using a transformer-based architecture and outperform existing state-of-the-art methods by a wide margin.

Published in Transactions on Machine Learning Research (06/2024)
Self-Improvement for Neural Combinatorial Optimization: Sample Without Replacement, but Improvement
Jonathan Pirnay
jonathan.pimay@tum..d
Technical University of Munich, TUM Campus Straubing University of Applied Sciences Weihenstephan- Triesdorf
Dominik G. Grimm
dominik dominik.grimmal/ (hswrt, hum)..aau
Technical University of Munich, TUM Campus Straubing University of Applied Sciences Weihenstephan- Triesdorf
Reviewed on OpenReview: https: // openreview. net/ formm? ad=
Abstract
Current methods for end-to-end constructive Neural Combinatorial Optimization usually train a policy using behavior cloning from expert solutions or policy gradient methods from reinforcement learning. While behavior cloning is straightforward, it requires expensive expert solutions, and policy gradient methods are often computationally demanding and complex to fine-tune. In this work, we bridge the two and simplify the training process by sampling multiple solutions for random instances using the current model in each epoch and then selecting the best solution as an expert trajectory for supervised imitation learning. To achieve progressively improving solutions with minimal sampling, we introduce a method that combines round-wise Stochastic Beam Search with an update strategy derived from a provable policy improvement. This strategy refines the policy between rounds by utilizing the advantage of the sampled sequences with almost no computational overhead. We evaluate our approach the Traveling Salesman Problem and the Capacitated Vehicle Routing Problem. The models trained with our method achieve comparable performance and generalization to those trained with expert data. Additionally, we apply our method to the Job Shop Scheduling Problem using a transformer-based architecture and outperform existing state-of-the-art methods by a wide margin.
1 Introduction
Combinatorial Optimization (CO) plays critical role in many real-world applications in fields diverse logistics, manufacturing, genomics and synthetic biology (Sbihi & Eglese, 2010; Crama, 1997; Naseri & Koffas, 2020). In CO problem, the goal is to find the best solution from finite set of options that maximizes a given objective function. The NP-hard nature of these problems and their complex variations make them exceptionally difficult to solve. Traditional methods for solving CO problems typically rely on exact algorithms, heuristics, and metaheuristics based on decades of research. Fxact algorithms such as enumcration, cutting planc, and branch-and-bound solve CO problems to optimality, but are limited by NP-hardness (Laporte, 1992). On the other hand, algorithms, and ant colony optimization can provide solutions faster without guaranteed quality (Crama et al., 2005; Yang, 2010; Dorigo et al., 2006). While powerful, the traditional methods struggle with scalability, computational efficiency, and adaptability to other problems. In addition, designing algorithms for a CO problem requires expert intuition and significant. domain knowledge (Vesselinova et al., 2020).
algorithms such as local search, genetic
To overcome those limitations, the success deep learning has led the emergence of Neural Combinatorial Optimization (NCO), which departs from traditional CO methods to leverage the pattern recognition and generalization capabilities of neural networks (Bengio et al., 2021). NCO aims to build models that

---

Published in Transactions on Machine Learning Research (06/2024)
generate approximate solutions to CO problems by learning from data without manually crafting algorithmic rules.
A prominent paradigm in NCO is the constructive approach, where a solution to a problem is built step by step in a sequential decision-making process. A neural network models the policy that guides these incremental decisions. This policy network is typically trained either by supervised learning (ST.) (Vinyals et al., 2015; Joshi et al., 2019; Fu et al., 2021; Kool al., 2022; Hottung et al., 2020; Drakulic et al., 2023; Luo et al., 2023) by reinforcement learning (RL) (Bello et al., 2016; Kool et al., 2019b; Nazari et al., 2018; Chen & Tian, 2019; Ahn et al., 2020; d O Costa et al, 2020; Hottung & Tierney, 2020; Kwon et al., 2020; Ma et al., 2021; Kim et al., 2021; Park et al., 2021; Wu et al., 2021; Park et al., 2022; Zhang et al., 2020; Hottung et al., 2022; Zhang et al., 2024). SL-based methods use expert solutions as labeled data for behavior cloning. While this training scheme is simple and effective, obtaining sufficient high-quality solutions from (exact) solvers can be expensive or even impossible for complex problems. On the other hand, RL methods exploit the natural modeling of the sequential problem as a finite Markov decision process, where the objective function is used as an episodic reward lo maximize. In contrast to ST, methods, they do not require pre-generated solutions but can suffer from strong hyperparameter sensitivity (Schulman et al., 2017; Henderson et al., 2018) and sparse rewards. Stato-of-tho-art RL methods for NCO perform remarkably on the training distribution but generalize poorly to larger instances (Kwon et al., 2020; Luo et al., 2023): typically, the policy is trained with REINFORCE (Williams, 1992), where gradients are accumulated over full trajectories. This results in high memory requirements; hence, the autoregressive decoder of the underlying architecture is usually lightweight. Luo et al. (2023) and Drakulic al. (2023) recently attributed the poor generalization ability to exactly the lightweight decoder of the used architectures (Drakulic et al., 2023; Luo et al., 2023). They show that increasing the size of the decoder structure and moving towards decoder-only architecture addressos this issue and leads to superior generalization performance. However, the network's ''s size makes it impractical to train the policy with the commonly used RL methods.
To be able to train those larger architcctures without expert data, we propose in this paper a simple, problen-inndependett training scheme on the intersection of RL and SL: We decode a set of solutions for randomly generated problem instances in each epoch using the current model. The solution with the best objective function evaluation for each instance is treated sequence of incremental decisions). Like decoder-only models in natural language processing (NLP), train the policy on these pseudo-expert solutions in a next-token prediction manner. By repeating this process, we create a 'sell-immrovinu loop. While self-improving models by training them on their own output have been proposed in the context of NLP (Huang et al., 2023), our training strategy constitutes a novel proposition for NCO.
pseudo-ezpert solution (corresponding to a
The effectiveness of this strategy relies on the quality of the decoded solutions and the efficiency of the underlying sampling process. In particular, we want to sample as few sequences as possible to get better and better solutions in each epoch. While repeated sampling from the conditional distribution given by the model at each soquential step works in principle, it can result in a set of sequenees that lacks diversity, contains numerous duplicates, and requires a large number of samples to find a solution that enables the network to improve. In this paper, we propose a sampling mechanism based on batch-wise Stochastic Beam Search (SBS) (Kool et al., 2019c) as introduced by (Shi et al., 2020). The mechanism draws samples without replacement in multiple rounds while maintaining a scarch tree. We suggest taking advantage of the batch- and round-wise mechanism to enhance its elfectiveness. Given the sequences sampled in a single round, we estimate the expected value of the objective function and update the trie with the advantage of the sampled sequences, a strategy derived from a provable policy improvement operation. Furthermore, to balance the explore-exploit tradeoff, we couple this update strategy with Top-p (nucleus) sampling (Holtzman et al., 2020). After each round, we gradually increase p < 1 to allow more unreliable sequences. Our method applies to any constructive neural CO problem, unlike sampling strategies that leverage problem specifics to diversify and improve the sampled solutions (Kwon al., 2020).
On the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), we demonstrate that training state-of-the-art architectures with our introduced method Gumbeldore (GD)* can
In homage Stochastic Beams and where to find them (Kool et al., 2019c).
2

---

Published in Transactions on Machine Learning Research (06/2024)
produce policies of comparable strength to those trained with expert trajectories from solvers. In addition, we train a transformer-base based architecture for the classical Job Shop Scheduling Problem (JSSP) using our method. Our results outperform the current state of the art by a wide margin.
Our contributions are summarized as follows:
(i) We propose a novel 'self-improvement training strategy for NCO on the intersection of RL and SL. In each epoch, we decode a set of solutions from the current policy and treat the best sequences found as pseudo-expert trajectories on which we train the policy in next-token prediction manner.
(ii) For sequence decoding, we propose novel method based on drawing the sequences in multiple rounds using batch-wise SBS. We develop a technique to make the underlying search tree more informed in each round by updating the sequence probabilities according to their advantage. Informally, we increase (decrease) the probability of better (worse) trajectories than expected. This update adds next to no computational overhead to the sampling method, and we derive this technique from a provable policy improvement.
(iii) We show the TSP and CVRP that our self improveentt method achieves comparable results to direct training on (near) optimal expert trajectories.
(iv) We present novel transformer-be based architecture for the JSSP that outperforms the current state of the art when trained with our method.
Our code for the experiments, data, and trained network weights are available at https://github.com gr grimmlab/ gutb//dobbel..r..
2 Related Work
Learning constructive heuristics Initiated by Vinyals et al. (2015) and Bello et al. (2016), the constructive approach in neural CO uses neural network (policy) to incrementally build solutions by selecting one element at a time. The most prominent way to train the policy network without relying on labeled data has become policy gradient methods in RI, notably using REINFORCE (Williams, 1992) with self-critical training (Rennie et al., 2017), where the result of a greedy rollout is used as a baseline for the gradient (Kool et al., 2019b). large body of research focuses on keeping the network architecture fixed and instead improving the self-critical baseline and gradient estimation by diversifying the sampled solutions (Kool et al., 2019a; Kwon et al., 2020; Kool et al., 2020; Kim al., 2021; 2022), often by exploiting problem-specific symmetries. For example, POMO (Kwon et al., 2020), one of the strongest constructive approaches, achieves diversity in routing problems by rolling out the model from all possible starting nodes of an instance. For the policy network, the Transformer (Vaswani et al., 2017) has become the standard choice for many CO problems (Deudon et al., 2018; Kool et al., 2019b; Kwon et al., 2020; Zhao et al., 2022) and is also used exlensively in this work. However, current RL-based methods struggle to generalize to larger instances (Joshi et al., 2020), possibly due to their prevalent encodrrddecode structure, where heavy encoder and light decoder facilitate training with policy gradient methods but limit scalability. On the other hand, recent work suggests that a lighter encoder with a heavier decoder can significantly improve generalization results (even with greedy inference only) (Drakulic et al., 2023; Luo et al., 2023), albeit at the cost of increased (if not, prohibitive) computational complexity for training with RL.
Self-improvement in neural CO The eross-entropy method (De Boer et al., 2005; Rubinstein, 1999) is a derivative-free optimization technique for a single problem instance that can be summarized as generating a sot. of solution candidates, evaluating them according to some objective function, and selecting the best-performing candidates to guide the generation of new solutions. While this principle of pushing the policy toward better performing sampled solutions lies at the heart of the self-critical policy gradient methods, there is little work on directly cloning the behavior of trajectorics (from multiple instances) sampled from the current model in neural CO (Bogyrbayeva el al., 2022; Bengio et al., 2021). In fact, independent of our work, Corsini et al. (2024) make the same observation. They present a 'seel-labeling' strategy that samples multiple solutions from the current policy and uses the best one as a pscudo-label for supervised training. However, they focus only on the JSSP and use vanilla sampling with replacement, in contrast to our main contribution, which updates the policy during the sampling without replacement process. We refer to Appendix E. for a deeper
3

---

Published in Transactions on Machine Learning Research (06/2024)
comparison. Furthermore, Luo et al. (2023) show a hybrid problem-specifie way to learn without any labeled data by pre-training randomly initialized model with RL on small instances, followed by reconstructing partial solutions to refine an unlabeled training dataset. We show that we can outperform this strategy without relying on RL.
Improving at inference time Closely related to our proposed sampling methods are approaches that use inference-lime search methods (other than greedy and pure beam search) to improve the generaled solutions. While the aforementioned problem-specifie diversification of POMO falls into this category, Choo et al. (2022) propose a beam search guided by greody rollouts. Active Search (Bello et al., 2016) and EAS (Hottung et al., 2022) update (a subset of) the policy network parameters for individual instances using gradient descent. The tabular version of FAS is reminiscent. of our approach by forcing sampled solutions to be close to the best solution found so far. MDAM (Xin et al., 2021) and Poppy (Grinsztaju et al., 2024) maintain population of policies, while COMPASS (Chalumeau et al., 2024) learns a distribution of policies that is searched at test time. However, these search methods are designed only for test time to exploit a pre-trained model or require a significant computational budget on the order of minutes per instance. This makes them impractical in our sell-improving setting, where we require trajectories that may live for only one epoch.
3 Learning Algorithm
In the following section, we formally set up the problem and present our proposed overarching self improvement learning method.
3.1 Problem Setup
This paper considers CO problem with T E decision variables of finile domain. Let X' be some distribution over the problem instances. For each instance x X, we assume that we can construct a feasible solution sequentially by assigning a value aj to the first variable, then 02 to the second, and so on, until we arrive at a complete trajectory 01.7
Sz. where Se is the set of all feasible solutions. Given an objective function fa: S, + R that maps feasible solution to real scalar, the goal is to find arg es,, (airr).
The corresponding neural sequence problem is to find a policy parameterized by 0 and factorized in condi- tional distributions (i..., the probability of a decision variable given the previous sequence), that maximizes the expectation Em=xEa, [fz (ai:))) where we have the total probability <o(a1:) = I mo(aela1=-1).
Here, for consistency of notation, we write a1:0 for an emply trajectory. We assume that we can sample from X, and usually, X' is chosen as a uniform distribution (e.g., for TSP, uniform distribution of points over the unit square from which we can sample random nodes). The policy To is a sequence model that defines valid probability distributions over partial and complete sequences. In the following, we omit the parameter 0 in the subseript and also refer to the decision variables as tokens by the terminology of sequence models. Tn particular, use the terms 'sequence", "trajectory' and 'solution' interchangeably.
3.2 Self-Improvement
We describe our proposed simple self- taff-improving training scheme in Algorithm 1. We generate a set of random problem instances each epoch and use the current best policy network to sample multiple trajectories for each instance. We add cach instance and the corresponding best trajectory to the training datasot, from which the network is trained by imitation of the trajectories. In particular, we train the poliey to predict the next token from a partial solution using a cross-entropy loss. At the end of the epoch, if the policy performs better when rolled out greedily than the currently best, we empty the dataset again (as we expect the sampled solutions to improve). Otherwise, the dataset will expand in the next epoch, providing the model with more training data.
The efficiency of the training determined by the sampling method in line 7, highlighted in bold. The goal is obtain a good solution with few samples m, balancing exploration and exploitation. Naively sampling sequences with replacement (i.e., Monte Carlo i.i.d. sampling, choosing the next token a with probability
4

---

Published in Transactions on Machine Learning Research (06/2024)
Algorithm 1: Self-improvement training for neural CO
Input: X: distribution over problem instances; fx: objective function
Input: n: number of instances to sample in each epoch
Input: m: number of sequences to sample for cach instance
Input: VALIDATION ~ X: validation dalaset
Randomly initialize policy mo
Theat <- π
current best policy
DATASET (
foreach epoch do
Sample set of n problem instances INSTANCES ~ X'
foreach I E INSTANCES do
Sample set of feasible solutions A == {a i
(m) 1:7 Abest
DATASET DATASET U ((1, arg max La (a(()))))
add best solution
foreach batch do
Sample B instances and partial solutions (1)
Lidd = (a (1) ......),) .o4)) with dj < T from DATASET for
10
j E B)
Minimize batch-wise loss Lo = - E log 2o (a()) ()) 1
11
b. next-token prediction
12
if greedy performance of my on VALIDATION better than Thest then
13
Thest f Tg
b update best policy
14
DATASET +
b. reset dataset
((al(a)--1) can lead to homogeneous (often differing in single token only (Li et al., 2016; Vijayakumar et al., 2018)) solution set with many duplicates. For example, Shi et al. (2020) show on a pre-trained TSP attention model (Kool et al., 2019b) that sampling 1280 sequences with replacement leads to 888 duplicate sequences for instances with 50 nodes, and still ~17% duplicate sequences for instances with 100 nodes.
4 Sample Without Replacement, but Improvement
In this section, we describe our main contribution, way to sample sequences without replacement multiple rounds as described in Shi et al. (2020), coupled with a policy update after each round. We begin with a recall of Stochastic Beam Search (Kool et al., 2019c) using the Gumbel Top-k trick (Gumbel, 1954; Yellott Jr., 1977; Vicira, 2014), followed by description of how to split the process into multiple rounds using an augmented trie, as described by Shi et al. (2020). We then describe how lo combine the trie with policy update. In the following, we use the term "beam search' to refer to the variant of beam search common in NLP, where nodes in the tric correspond to partial sequences, and a beam search of width k keeps the top most probable sequences at each step, ranked by the total log probabiiitt log π ((a=)) = Ei= log T (ay (1).
4.1 Preliminaries
Stochastic Beam Search SBS a modification of beam search that uses the Gumbel Top-k trick sample sequences without replacement by using Gumbel perturbed bog-probabilities. SBS starts at the root node (i.e., empty sequence) 01:0 and sets the root perturbed log- log-probability Gain := 0. Now, at any step during the beam search, let aizt be a partial sequence with score Ga... Then, for direct child a1æ+1 E Children(a1.)) we sample the perturbed log-probability Gaitzr ~ Gumbel π ((1a+1)) from a Gumbel distribution with location log ( (a):++) under the condition that max EChildrem(asss) Ga Garc and use the Ga 's as the scores for the beam search. By requiring that the maximum the perturbed log pog-robabillties of sibling nodes must be oqual their parent's, sampled Gumbel noise consistently propagated down the subtroc. Kool et al. show that this modified beam search is equivalent to sampling i sequences without replacement from the sequence model म, yielding diverse but high-quality sequences. Since SBS performs the expansion
5

---

Published in Transactions on Machine Learning Research (06/2024)
of the beam in regular deterministic beam search, it can be parallelized in the same way. We provide detailed summary of the underlying theory in Appendix A.
Incremental Sampling Without Replacement Shi et al. (2020) present an incremental view on sampling sequences without replacement that can draw one sequence after another. They suggest maintaining an augmented trie structure that grows with the sampling process, where nodes correspond partial sequences in beam scarch. Starting from the root node (representing an empty sequence), single leaf node 01.7 (representing complete sequence) is sampled from the sequence model x. Then the total probability of T(a):)) is recursively subtracted from the probability of the leaf and its ancestors (which correspond to all partial sequences 01:0, 01:1...., Q1:T). After renormalization of the probabilities, the trie represents a sequence model from which 01:T has been removed, and re-sampling from this updated trie is equivalent to sampling from the model conditioned on the fact that 01.r cannot be selected (see Figure 1). The incremental nature of the process has the advantage that we can sample continuously without replacement, stopping only when some condition is met. To further exploit the parallelism advantages of SBS, Shi et al. (2020) suggest combining SBS with their method: Instead of drawing just one sequence, we use the same trie for SBS and draw batch of k samples in parallel. Then, the recursive probability update done for all l sequences. This allows us to sample batches rounds, e.g., with a beam width and n rounds, we sample k n soquences without replacement. Note that although we must maintain trie structure, each round of SBS maintains the constant memory requirements of beam search of width k.
0.09
0.3
0,2
0.5
0.5
0:09
0.5
A
B
0.06
0.03
0.11 BOG
0:03 BDC
0.0
BDC
BBG
4.2 Sampling with Gumbeldore
Figure Example of incremen- tal sampling using trie. Nodes represent partial sequences (here, letters) and contain their total probabilities. i.) The sequence 'DG' is sampled from the model, and we subtract its total proba- bility from its ancestors. ii.) Up- dated trie after crasing 'BDG'.
In the following, let X be problem instance, and let & be the beam width for SBS and the number of rounds. For sampling from policy in Algorithm above, we use the batch-wise sampling in n rounds to draw k n sequences without replacement. Suppose that in the first round we sample complete trajectories i......., air with SBS. The question arises since we already have k complete trajectories, and thus their evaluations (t) (a)) R. can get information about their quality and use it in the would
a
next round of SBS? Inluitively, for the next round of sampling, like to move in the trie from π to a policy n' that puts more emphasis on tokens that have led to 'good' solutions and less emphasis on tokens that have led to 'not-so-oood' solutions.
4.2.1 Trie Update
Thcoretical Policy Improvement To theoretically motivate our approach, consider any complete
trajectory a1.7 = (aI....,ay aT)) and policy म. We can move to an improved policy by shifting the unnormalized log- bog-prbbabylity ('logit') of the intermediate tokens of a1. by their individual advantage. That is, for E [,....T), we set,
logit x'(a;/an=-1) == log (1)
(1)
Eag B - (1ns) [fa(a Eag ( -
(fa(a):))] (f
advantage of token a;
Here, o > O is a predefined size of the update step, and d'irr x(-la1s) denotes a complete sequence d'.r= (a',,.., af) drawn from я where df = aj for all j E (]....,a]. Informally, (1) increases the probability of tokens that have a better expected outcome than their parent and decreases it otherwise. Formally, (1)
yields a policy improvement, i.e., we get
Earrwn [fa(a 2 Earros [f(())))
(2)

---

Published in Transactions on Machine Learning Research (06/2024)
and we provide proof of this in Appendix B.
Practical policy update Tet a.,,...,,, (*) be & complete trajectories sampled with SBS, which assume to be ordered by their perturbed log-probabilities Ga 2 ... Ga We have omitted 1 I" in the subscript for case notation. Motivated by its provable improvement, we would like to apply (1) to all a but the update relies on our ability estimate the corresponding expectations. Kool et al. (2019c) present an unbiased estimator of the objective function expectation of the sequence model:
TT((1))
Earray [f ~
Σ wa (a (=al)) where waw (a
{a(+) (a()))
(a (a) P(G > ())) is the probability that the i-th perturbed log- prrbaabbbbity is greater than the k-th largest. In practice, the normalized variant (which biased but consistent)
and la
(00)== = Eisl Wa (a EE ( (a(*)
p(a ,..,, (1))
(4)
is preferred to reduce variance. Note that (4) estimates the 'full' expectation from emply sequence. However, since in SBS, the maximum of the perturbed log brobbbbbbllisss of sibling nodes is conditioned on their parent, we can also estimate the expectation starting from other partial sequences: For any sequence bis5 of length j,
let 5(bi,)) == {a (mx)) (m.......... (m)) (a a { (again ordered by their perturbed log-probabilities) be (m1)
the subset of all sampled sequences that share the subsequence bı.j- Le., we have bı.j ai. Then,
ai.
(m²)
(a [f((a)))] p(a (m11) ,..., ....,a!m! (mi))
estimates the expectation of the objective function given big- While we use this approach to apply (1) to the logits of any (99), it has major drawback: Depending on the length T of the problem, the beam width k and the confidence of π, in practice the sampled sequences will rarely share a long subsequence, which makes hard to properly estimate the expectation of nodes deep in the trie.
()) .....,"....""... ((..())......))) which we propagate up the trie at. the same time as we mark ( sampled. Overall, the trie update after each round of sampling can then be summarized follows: For all i E {L....,,k] k}, compute the global advantage Aato fz (2) ((a .i.....tt, (k),, and update the logit for each j E (1....,T") ... via
So we take practical approach and only use the 'global' advantage
logit 7' <'(0, 1a = log T
( (1-1))-
Σ T(b) (E
to Σ Ab.
(6)
BES(a
We illustrate an example the trie update after each round in Figure 2. We note that as all expectations are obtained via (4), the update (6) adds no significant computational overhead to the round-based SBS. When samling another k sequences in the next round, we repeat the process. In Appendix C.I, we experimentally compare the theoretical update (1) with the practical update (6), and see that while both yield strong results, (6) is almost always more favorable in practice.
Choice of step size o The update (6) scales the probabilities by exp(a Σ As), so the role of the hyperparameter is mainly to dampen the advantage. Since the magnitude of Σ Ab usually also changes as the policy π evolves, the choice of is highly problem-dependent. In particular, one could think of, e.g., transforming the Ag by min-max normalization or changing during training optimize the behavior of the update. However, our experiments use the pure advantages and a constant, small problem-dependee o throughout the training process (see Section 5.3).
7

---

Published in Transactions on Machine Learning Research (06/2024)
103
(0.4 - 0.1) (xp(-2)
(0.3 - 0.1 0.11 exp(2+
0.3
0.3
0.4
(0.3
0.2)
0.3
0.0
0.02
0.98
0.05
0.05
000
0.01
0.01
10.0
0.96
3
8
3
6
8
2
5
5
6
7
5 1
4.7
fa
Figure Example of update (6) with beam width A: = 3 and a= 1. Nodes represent partial sequences and their total probabilities; the numbers {I,...,9) 9} below the leaf nodes are their corresponding objective function evaluation. i.) We sample leaf nodes with SBS and obtain the objective function estimate μ with (4). ii.) We mark cach lcaf as sampled by removing its total probability from its ancestors. At the same time (equivalent to adding to the log- log-rrobability). exponential of the leaf's advantage. iii.) Trie after normalization, corresponding to n'.
multiply the ancestors' reduced probability by the
Algorithm 2: Sampling with Gumbeldore (GD)
Input: x ~ X: problem instance; fz: objective function; policy
Input: k: beam width for SBS; n: number of rounds
Input: a: policy update step size; Pmin: minimum nucleus size
Output: Sampled sequence with highest f
SAMPLED +0
for i i= l,....Ph do
p (1 i-1
n-1 Puin +
1-1 n-1
SBS with n, beam width k and nucleus SAMPLED + SAMPLED (air..... a a.r)
01.T d:T +
Obtain B [f] estimate P - ((a(1) ( n' +
(t)) via (4)
for j = 1, I...., do
9
for m I,...,7 do
10
S + (((
(i) C {a (1)
i .....
1:7)
(k)
D sequences with same first m tokens (1)m-1) EbES n(b)) Ebes(((b)) 1)
logit n' (amm) |a (m1m-)) log (T(mi))
(i)
(1)
11
12
Return arg max aESAMPLE s(a)
4.2.2
Growing Nucleus
To further exploit the round-based sampling strategy, truncate the conditional distributions T(-[a1:) using Top-p (nucleus) sampling (Holtzman et al., 2020) at each beam expansion in SBS with varying p. If n > 1 is the number of rounds, then we set p for the i-th round with < < to
i 1-1 Pmin n n-1 We start at a predefined 0 < Pmin and lincarly incrcase p to 1. The idca that truncating the "unreliable tail' of 7--(a12) with p may be desirable in later stages of training further exploit the model. However, if the model is unreliable, especially in the early stages, we want to consider the full distribution to encourage exploration. By gradually increasing p, we accommodate both cases, while the trie policy update helps keep good choices in the nucleus and pushes bad ones out. In practice, we start with Puin = 1 and set Pinin 0.95 after several epochs. When sampling at inference time, an even smaller Pminn can improve the results (ef. Appendix C.3). During training, however, we found that using Pmin < 0.9 leads to the model converging prematurely as it only learns to amplify its decisions.
i i-
We summarize the complete sampling strategy in Algorithm 2.
8

---

Published in Transactions on Machine Learning Research (06/2024)
5 Experimental Evaluation
We are pursuing two experimental goals: First, we want to evaluate the effectiveness of our method within the entire training cycle of the sell-improvement stralegy (see Algorithm 1), and we test it on three CO problems with different underlying network architectures: the two-dimensional Euclidean TSP, the CVRP, and the standard JSSP. Second, as the training relies on the effectiveness of the solution sampling, we want to assess the solution quality of our sampling strategy (especially with a low number of samples). We take various network checkpoints of all three problems and compare different sampling techniques with our proposed method.
5.1 Routing Problems
We consider two prevalent routing problems, the two-dimensional Euclidean TSP and CVRP, where the construetive approach builds a tour by picking one node after another. For both problems, we reimplement the transformer-based architecture from the recent Bisimulation Quotienting (BQ) method (Drakulic et al., 2023). This model has nine layers that process the remaining nodes each step. In the original work, due to its size, BQ is trained on expert trajectories from solvers with N = 100 nodes. The authors report excellent. results on the training distribution and superior generalization on larger graphs with N E {2000, 500, 1000} nodes. We train the network on instances with 100 nodes in the same supervised manner. In addition, we train it with two variants of our proposed self-imprveemett method, where we sample trajectories without replacement using (a) simple round-wise SBS (SI WOR), and (b) the proposed Gumbeldore method (ST GD). The setup is briefly outlined below. For implementation details and hyperparameters, please refer to Appendix D.2 and D.3. Furthermore, the 'Light Encoder Heavy Decoder' (LEHD) by (Luo et al., 2023) follows a similar paradigm to BQ. Apart from supervised learning, they show problem-specific way to learn the TSP without any labeled data. We discuss this method in Appendix C.2 and demonstrate that S1 GD outperforms it.
Datasets and supervised training Training (for supervised learning), validation, and test data are generated in the standard way of previous work (Kool et al., 2019b) by uniformly sampling N points from the two-dimensional unit square. The training dataset consists of one million randomly generated instances with - 100 nodes for TSP. The validation and test sets (also N = 100) include 10,000 instances cach. The test set is the same widely used datasel generated by Kool et al. (2019b). For N E (200, 500, 1000), we use a lest. set of 128 instances identical to Drakulic et al. (2023). For supervised training and to compute optimality gaps, we obtain optimal solutions for the generated instances with the Concorde solver (Applegate 2006). For the CVRP, the datasets have the same number of instances, and use the same sets as in Luo et al. (2023), where solutions come from HGS (Vidal, 2022). The vehicle capacities for 100, 200, 500, and 1000 nodes are 50, 80, 100, and 250, respectively. The supervised model is trained by imitation of the expert solutions using a cross-entropy loss. We sample 1000 batches of 1024 sub-paths in each epoch, following Drakulic el al. (2023). The model is trained until we have yet. to observe any improvement on the validation set for 100 epochs (in total ~4.5k epochs for TSP and 11.3 for CVRP). We note that we can reproduce (up to fluctuations) the results from the original work.
al.,
Self-improvement training For both SI WOR and SI GD, we generate 1,000 random instances in each epoch. Per instance, we sample 128 solutions in n 4 rounds with a beam width of k = 32. For SI GD, we set the constant a to scale the advantages to a 0.3 for the TSP and to a 3 for the CVRP. We refer to Appendix D.1 for how we obtained these values. For SI GD and both routing problems, we start with Pmin = 1 (no nucleus sampling) and set Pmin = 0.95 after 500 epochs. Training on the generated data is performed in the same supervised way (in total ~222 epochs for TSP and ~2.7k for CVRP). Interestingly, SI GD takes fewer epochs on the TSP and more on the CVRP than SL, confirming that it is much harder to learn houristics from scratch for the CVRP. Our method cannot access optimality information, so we compare model checkpoints by their average tour length on the validation set..
Inference and baselines All evaluations are performed with the model trained on N 100. We are mainly interested in how the self-improving model performs compared to its supervised counterpart (BQ ST.)
9

---

Published in Transactions on Machine Learning Research (06/2024)
Table Results for the routing problems, with emphasis on the BQ architecture. 'Gap' the optimality gap w.r.t Concorde (Applegate al., 2006) for the TSP and HGS (Vidal, 2022) for the CVRP. 'Time' is the time needed to solve all instances. Models are trained on instances with N 100 nodes and used evaluate generalization to N (200, 500, 1000) nodes. 'beam' refers to beam scarch of given width.
Method
Test (10k inst.)
Gencralization (128 instances)
TSP N
100
TSP N
200
TSP N
500
TSP N
1000
Gap
Time
Gap
Time
Gap
Time
Gap
Time
OR-Tools
2.90%
1h
4.52%
6m
4.80%
30m
5.02%
3h
AM, beam 1024
2.49%
5m
6.18%
15s
17.98%
2m
29.75%
7m
MDAM, beam 50
0.40%
20m
2.04%
3m
9.88%
12m
19.96%
1h
POMO, augx8
0.14%
15s
1.57%
2s
20.18%
16s
40.60%
3m
SGBS
0.06%
8m
0.67%
30s
11.42%
10m
25.25%
1.5h
BQ SL, greedy
0.40%
30s
0.60%
38
0.98%
16s
1.72%
32s
BQ SL, beam
0.02%
8m
0.09%
30s
0.43%
4m
0.91%
10m
BQ SI WOR (ours), greedy
0.44%
30s
0.73%
3s
1.39%
16s
2.34%
32s
BQ SI WOR (ours), beam 16
0.03%
8m
0.11%
30s
0.53%
4m
1.16%
10m
BQ SI GD (ours), greedy
0.41%
30s
0.64%
3s
1.12%
16s
2.11%
32s
BQ SI GD (ours), beam 16
0.02%
8m
0.10%
30s
0.46%
4m
1.01%
10m
CVRP N 100
CVRP N 200
CVRP N
500
CVRP N
1000
Gap
Time
Gap
Time
Gap
Time
Gap
Time
OR-Tools
6.19%
2h
6.89%
1h
9.11%
2h
11.66%
3h
AM, beam 1024
4.20%
10m
8. 8.18
24s
18.01%
3m
87.56%
12m
MDAM, beam 50
2.21%
25m
4.30%
3m
10.50%
12m
27.81%
47m
POMO, augx8
0.69%
25s
4.87%
3s
19.90%
24s
128 82%
4m
SGBS
0.08%
20m
2.58%
50s
15.34%
12m
136.98%
2h
BQ SL, greedy
3.03%
2.63%
48
3.75%
22x
5.30%
48s
BQ SL, beam 16
1.22%
13m
1.15%
1m
1.93%
6m
2.49%
15m
BQ SI WOR (ours), greedy
3.93%
50s
4.11%
4s
4.87%
22s
8.47%
48s
BQ SI WOR (ours), beam 16
2.06%
13m
2.06%
1m 2.91%
6m
5.87%
15m
BQ SI GD (ours), greedy
3.26%
50s
3.05%
4s 3.89%
22s
8.33%
48s
BQ SI GD (ours), beam 16
1.72%
13m
1.58%
1m
2.32%
6m
5.57%
15m
and thus focus on greedy results. We also report the results using a beam search of width 16 by Drakulic et al. (2023) for coherence, Furthermore, we list the results of (a) Google's OR-Tools (Perron & Furnon, 2022) non-learning local search algorithm; (b) the prominent Attention Model (AM) (Kool al., 2019b) (with a beam search of width 1024), which was trained with self-critical REINFORCE. and forms the basis of most constructive methods for routing; (c) its multi-decoder version MDAM (Xin et al., 2021) (with a boam search of width 50), which trains multiple diverse policics; (d) POMO (Kwon et al., 2020) with its best inference technique (corresponding to 8NN diversified solutions per instance size N). (e) SGBS (Choo al., 2022), a pure inference technique based on beam search guided by greedy rollouts, backed by POMO with hyperparameters (3,7) which is considered the current sfate-of-theeart method of learning constructive heuristics from scratch. POMO performs impressively on the training distribution but has difficulties generalizing to larger instances. As our architectural setup is identical to BQ, we refer to the original work by (Drakulic et al., 2023) for comparison with various other methods.
to (10, 10) for the TSP and (4, for the CVRP. POMO
Table 1 summarizes the optimality gaps. Both SI WOR and SI GD show strong performance when compared training on expert trajectorics, with SI GD outperforming WOR. For the TSP, SI GD achieves results on par with its SL counterpart on the training distribution generalization capabilities. For the CVRP, while the results close to SL. on N 100, the generalivation
Results
100 and shows similarly strong
10

---

Published in Transactions on Machine Learning Research (06/2024)
difference becomes larger as N grows, with, for example, difference of ~ 3% on N = 1000. We note that generalixing to larger instances means not only larger N but also unseen vehicle capacities. Drakulic et al. (2023) analyze that the final performance of the model strongly depends on how an expert solution sorts the subtours. In particular, the model favors learning from solutions where the vehicle starts with subtours with the smallest remaining vehicle capacity al the end of the subtour (usually 0). Since we cannol guarantee during learning in our SI procodure that the vehicle is nearly optimally utilized in the subtours, we assume that this makes it more difficult for the model to generalize to unknown capacities. Nevertheless, the SI GD and SI WOR generalization results for CVRP still show the same strong dynamics as those of BQ SL, trained without any labeled data. This makes our method a promising alternative to RL.-based policy gradient methods, especially due to its simplicity.
5.2 Job-Shop Scheduling Problem
In a JSSP instance of size J x M, we are given J jobs consisting of M operations. Each job's operations must be processed in order (called a precedence constraint), and each operalion runs on exactly one of M machines for a given processing time (i.e., there is a bijection between a job's set of operations and the set of machines). The goal is to find schedule that processes all job operations without violating the job's precedence constraints and has minimum makespan (i.e., the completion time of the last operation). In our required sequential language, we represent feasible solution, i.e., a. schedule that satisfies all precedence constraints, as sequence of jobs, where each occurrence of a job means scheduling the next unscheduled operation of the job at the carliest possible time. In particular, the model predicts a probability distribution over all unfinished jobs at each step of constructing a solution.
Model We propose a novel pure transformer- based architecture inspired by the BQ principle (Drakulic et al., 2023) to train a model with our ST GD method. We consider a. JSSP instance as an unordered sequence of operations with positional information for operations belonging to the same job. We mask already scheduled operations at cach construction step and procoss the sequence through simple stack of pairs of attention layers. In each pair, we mask operations so that i.) in the first layer, only operations that belong to the same job can attend to each other, and ii.) in the second layer, only operations that need to run on the same machine can attend to each other. We describe the architecture in detail in Appendix D.4. To balance inference speed and model expressiveness, we settle on a latent dimension of 64, three pairs of attention layers with eight heads, and a foed-forward dimension of 256.
Datasets All random instances are generated in the standard manner of Taillard (1993) with integer processing times in [1]. Since we train our model only with our self- reffemmproveeett method, we pre- pre-generate validation set of 100 instances of size 20 x 20. We test the model on the well-known Taillard benchmark dataset (Taillard, 1993), computing optimality gaps to the best-known upper bounds.2
Self-improvement training We train the policy for 100 epochs with SI WOR and S1 GD. In each epoch, we randomly choose a size from (15 x 10, 15 x 15, 15 20) and sample 512 instances of the chosen size. We generate 128 solutions for each instance in 4 rounds of beam width 32. For ST GD, we use an advantage step size of 0.05 and set Pmin = 0.95 after 50 epochs. Similar to the routing problems, we sample 1,000 incomplete schedules (i.e., a partial sequence of jobs) of size 512 from the generated training data. We train the model to predict the next job to choose using a cooss-entropy loss. Please see Appendix D.4 for more details.
Inference and baselines We lest performance of the model by unrolling the policy greedily. Since SI GD shows the strongest greedy results, we further evaluate the trained model i.) with a beam search of width 16, fi.) SBS of beam width 16 with constant nucleus of p 0.8 and ffi.) sampling with GD to assess the efficiency of GD as inference technique. We compare our approach with (a) L2D (Zhang el al., 2020), an RI. single-agent method; (b) ScheduleNet. (Park et al., 2022), an RL multi-agent method. Both methods represent a JSSP instance as a disjunctive graph and train Graph Neural Networks (GNNs) with (variants of) PPO (Schulman et al., 2017); (c) The 500- and 5,000-step variants of L2S (Zhang et al., 2024),
2 Available http://optmiizzzer.com con/TA phpppppppppppppp.ppppp and http://jobsshop-jjee jjvh.mn
11

---

Published in Transactions on Machine Learning Research (06/2024)
Table 2: JSSP results on the Taillard benchmark set with eight different problem sizes. Our models SI WOR and SI GD are trained on instances of random sizes E {15 x 10, 15 x 15, 15 x 20), using the resulting model for all benchmark instances. The first group of results represents greedy inference, while the second group compares inference types with larger computation times. 'GD 32 4' refers to using GD sampling with four rounds of beam width 32, using Pmin = 0.8. 'SBS 16, 0.8' refers to sampling 16 sequences without replacement with a constant nucleus size of 0.8. For GD 32 x 4 and SBS 16, we report the mean actoss five repetitions. Best optimality gaps per group are indicated in bold.
15
15
20 x 15
20
20
30
20
50 15
50
26
100
Method
Gap
Time
Gap
Time
Gap
Time
Gap
Time
Gap
Time
Gap
Time
Gup
Time
Gop
Time
CP-SAT
0.1%
1,25h
0.2%%
8h
0.7%
10th
2.1%
10h
2.8%
10h
0.09%
2-1m
2,8%
9ba
3.9%
10ta
L2D. greddy
.0.0%
0=
30.0%
0=
31.6%
1s
33.0%
1s
53.63
25
22.1%
2s
26.5%
4-
13.0%
25c
SchoduleNet, grodyy
15.3%
191.4%
64
17:226
11s
19.1%
15s
23.7%
25s
13.99%
50%
13.6%
1.6mm
6.756
7m
SPN, greedy
13.8%
15.0%
0=
15.29
0s
17.1%
05
18.5%
1s
10.1%
11.6%
1-
5.9%%
2b
1:25, 300 steps
9.3%
11.6%
10k
12.44%
11s
14.7%
12%
17.5%
14s
11.0%
164
13.0%
23+
7.95%
301
SI WOR (ours), greedy
12.1%
1s
10.9%
1=
11.3%%
1s 10.7%
1s
13.6%
2>
3.9%
2s
7.9%
1.7%%
28s
SI GD (ours), greedy
9.656
9.9%
1s
11.1%
1s
9.5%
1s
13.8%
24
2.7%
6.7%
1.7%
L22,, 2000 steps
6.2%
1.5m
8.1%
1.Fmn
9.0%
1.5m
9.0%%
2m
12.6%
2.4m
4.85%
2.8m
6.5%
3.8m
3.0%
8.4m
SI GD (ours), besmn 16
10.1%
9.8%
2:
10.456
ds 8.5%
56
12.3%
10s
2.6%
18s
7.7%
40s
1.3%%
1.5m
SI GD, 8BS 16, y = 8.8
6.0%%
6.6%%
25
8.9%
4s
7.4%
10.5%
10s
1.7%%
18%
5.0%%
40s-
0.75%
1.5m
SI GD. GD 32 x 4
5.0%
5.6%
10s
7.0%
30s
5.8%
30s
9.2%
1.3m
1.1%%
2.
4.3%
3.5m
0.4%
9mm
strong GNN-guided improvement method that transitions between complete solutions at each step; (d) the concurrent work SPN (Corsini et al., 2024), which trains a Graph Attention Network in a self- ielf-inproving manner on sampled solutions (we refer to Appendix E. for a methodological comparison); and (d) as a non-learning baseline, the highly efficient constraint programming solver CP-SAT in OR-Tools (Perron & Furnon, 2022), with a time limit of one hour per instance, as reported by Zhang et al. (2024). As noted in most previous work on neural CO, a fair comparison of inference times is challenging, as they depend on the implementation (especially using deep learning frameworks) by orders of magnitude. In particular, we report the time required to solve the instances of given size (allowing parallelization) but compare the respective methods based on their inference type (e.g., treating greedy methods as equally computationally intensive).
Results We collect the results in Table 2. In the greedy setting, both SI GD and SI WOR out all three constructive methods, L2D, ScheduleNet, and SPN, by a wide margin and obtain smaller gaps than L2S with 500 improvement steps in all but one case. The quadratic complexity of our architecture becomes noticcable for 100 20. SI GD significantly improves SI WOR. When allowing for longer inference times, we compare our strongest model ST GD only with the strongest method, L.2S with 5,000 improvement steps. We note that our method does not always improve with beam search, with some results even worse than greedy. That sequences with high overall probability do not necessarily mean high quality is a ubiquitous effect in NLP (Holtzman et al., 2020), showing that the model is not as confident, as for the routing problems. Thus, we use the model obtained with ST GD and sample with SBS and a constant nucleus of p = 0.8. This maintains short inference times but outperforms L2S across all problem sizes. We can further improve the results by sampling with GD in multiple rounds (with Punin 0.8) and using our policy update. For more results and comparisons when using GD at inference time, see Appendix C.3.
5.3 Sampling Performance
We analyze the performance of GD as a sampling technique, especially when sampling only a small number of sequences. For this, we take the model weights from two checkpoints during training: One late in training, when the model has almost converged, and an intermediate one, when the model shows fair greedy performance but still has much room for improvement. Taking a checkpoint very early in training carries limited information, as the performance still depends strongly on weight initialization, and any sampling method with high exploration leads to substantial improvement. We then sample up to 640 sequences with an SBS beam width of 32 in up to n = 20 rounds (for sampling with replacement, we sample the equivalent number of 32- n sequences) and compare the optimality gap of the best sequences found. In Figure 3, we plot the results using our proposed method ('Gumbeldore') and for sampling with ('Sample WR') and without replacement ("Sample WOR'). To better understand the impact of the growing nucleus in Section 4.2.2, we
12

---

Published in Transactions on Machine Learning Research (06/2024)
TSP N 100. intermed model gready 4.00%
TSP N 200, late model, gready 0.5%%
CVRP N 100, Intermed lite modal gready 12.59%
CVRP K- 100, lace mrodel gready 3.27%
Sempi WeR 201
Sanvie 6814
Wilk jwa 2910
Semoda NOO (SCCIAA Par 1.0
1.2
3.32
15
Ramber
intermediite model groddy
JF0P 15x 15, model, 11.65%
155P 20x 20, intemmekgte model groedy 14.5%
[S5P 20 x20 Md+ moddll greedy 10.01%
Samon Wi
sung Wol tsudinu 1.0
Sumpa Usn -606, 6001
630)
sanple Mok bracess Aor 6000
carbatdon 666, 666)
0.20
Uoa (05)
Gyraddooe 0.000
12
15
burber ofrsande Deam 32
NumOrr coren (24e 52)
Figure 3: Sampling results for different training checkpoints, with the corresponding greedy performance of the model. For Sample WR, we sample 32 sequences with replacement, where n is the number of rounds. For TSP and CVRP, each data point corresponds to the average best solution across 100 instances. For JSSP, we evaluate the Taillard instances of the corresponding size. Sampling for each data point is repeated 20 times; shades denote standard errors.
also show the results for sampling without replacement with the growing mucleus, but without the policy update (6) ("Sample WOR (mucleus))). We note that applying only one round of Sample WOR (nucleus) or GD is identical to Sample WOR by design. We use the same value for a as during training, and show results for Pmin = 1 (no nucleus sampling) and Pmin = 0.95 (as during training).
In line with Shi et al. (2020), we observe that sampling WOR yields consistent but slight improvement over WR for the routing problems but is almost unobservable for JSSP, which has much longer sequence length (225 for 15 x 15 and 400 for 20 x 20). Generally, allowing different nucleus sizes can significantly improve the intermediate models while giving enough room for exploration. Updating the policy between rounds with GD has a strong impact, especially on the intermediate models. Coupling the policy update with a growing nucleus further improves the performance. For example, with only four rounds, we obtain an absolute improvement over Sample WOR of approx. 2% for CVRP and >1% for JSSP 20 x 20 and reach an optimality gap with only 128 samples, which Sample WOR does not reach with 640 samples. While generally shrinking for only few rounds, the relative improvement of GD is still significant in late models. In particular, GD consistently finds better solutions in late models when nucleus sampling only has limited influence. In Appendix C.4, we further illustrate the applicabilit, of our method on a toy problem: we adapt our method for the board game Gomoku (Five in a Row) and evaluate how long it takes to consistently beat a deterministic expert bot.
6 Limitations and Future Work
Adjusting the policy by the advantage requires choosing step size o,, which must be tuned for the problem class. To keep the approach principled, we left the step size fixed throughout training; however, the advantages' magnitude usually shrinks as training progresses. Hence, it might be advantageous to change a during training based on problem specifics or normalize the advantages as mentioned in Section 4.2.1. Our method requires keeping a search tree in memory instead of only one round of SBS, where we can discard all previous sequences after each step. However, keeping transitions in memory has benefits, such as only evaluating the policy when needed and thus reducing computation time during search.
13

---

Published in Transactions on Machine Learning Research (06/2024)
7 Conclusion
In this work, we introduced approach for training Neural Combinatorial Optimization models that bridges supervised learning and reinforcement learning challenges. During training, GD finds good solutions with only few samples, eliminating the need for expert annotations while reducing computational demands. This method simplifies the training process and shows promise for onhancing the efficiency of Neural Combinatorial Optimization using larger archilectures.
Acknowledgments
We thank the Action Editor and the anonymous reviewers for their constructive feedback. This work was funded by the Deutsche Forschngsgemeisscaatt (DFG, German Research Foundation) 466387255 within the Priority Programme "SPP 2331: Machine Learning in Chemical Engineering'. The authors gratefully acknowledge the Competence Center for Digital Agriculture (KoDA) at the University of Applied Seiences Weihenstephan-TTiees Triesdorf for providing computational resources.
Code Availability
Code for the experiments, data, and trained network weights are available at attps://gitte com com/grimmlab// gumbeldore.
References
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what to defer for maximum independent sets. In International conference on machine learning, pp. 134-144. PMLR, 2020.
D.L. Applegate, R.E. Bixby, V. Chvatal, and W.J. Cook. The traveling salesmon problem: computational study, Princeton University Press, 2006.
Thomas Bachlechner, Bodhisattwa Prasad Majumder, Henry Mao, Gary Cottrell, and Julian McAuley. Rezero is you need: Fast convergence at large depth. In Uncerteinty in Artificial Intelligence, pp. 1352-1361. PMLR, 2021.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning, arXiv preprint arXiv:1611.099/ 2016.
Yoshua Bengio, Audrea Lodi, and Antoine Prouvast. Machine learning for combinatorial optimization: methodological tour d'horizon. European Journal of Operational Research, 290(2):105 121, 2021.
Aigerim Bogyrbayeva, Meraryslan Meraliyev, Taukekhan Mustakhov, and Bissenbay Dauletbayev. Learning solve vehicle routing problems: A survey, arXiv preprint arXiv:2205.02/3 2022.
Felix Chalumeau, Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, and Tom Barrett. Combinatorial optimization with policy adaptation using latent space search. Advances in Neural Information Processing Systems, 36, 2024.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in neural information processing systems, 32, 2019.
Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tierney, and Youngjune Gwon. Simulation-guided beam search for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35:8760-877 8772,, 2022.
Andrea Corsini, Angelo Porrello, Simone Calderara, and Mauro Dell' Amico. Self- the job shop scheduling problem. arXiv preprint arXiv:2/01.11849, 2024.
Yves Crama. Combinatorial optimization models for production scheduling in automated manufacturing systems. European Journal of Operational Research, 99(1):136-153 153,, 1997.
Yves Crama, Antoon WJ Kolen, and EJ Pesch. Local search in combinatorial optimization. Artificial Neural Nelworks: An Introduction to A ANN Theory and Practice, pp. 157-174, 2005.
14

---

Published in Transactions on Machine Learning Research (06/2024)
Paulo Rt d O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay, Learning 2-opl heuristics for the traveling salesman problem via deep reinforcement learning, In Asian conference on machine learning, pp. 465-4801 PMLR, 2020.
Ivo Danihelka, Arthur Guez, Julian Schrittwieser, and David Silver. Policy improvement by planning with gumbel. In- ternational Conference Learning Representations, 2022. URL httpp:///ppeeeeeeeeeeeeeoooounnm
net/forum? http:/frrumnddbbaaaaa d-bERaNdoegn..
Pieter-Tjerk De Boer, Dirk P Kroese, Shie Mannor, and Reuven Rubinstein. A tutorial on the cross-enlropy method. Annals of operalions research, 134:19 67, 2005.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis- Rousseau. Learning heuristics for the tsp by policy gradient. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 29, 2018, Proceedings 15, pp. 170-181. Springer, 2018.
Marco Dorigo, Mauro Birattari, and Thomas Stutzle. Ant colony optimization. IEEE computational intelligence magazine, 144):28 2222,299--99 2006.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Audreoli. Bq-uco: Bisimulation quotienting for efficient neural combinatorial oplimization. In Thirtg-severtth Conference on Newral Information. Processing Systems, 2023.
Zhang-Hur Hua Fu, Kai- Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference artificial intelligence, volume 35, pp. 7474-7482, 2021.
Nathan Grinszlaju, Daniel Burelos-Blanco, Shikha Surana, Clément Bonnet, and Tom Barrett. Winner takes all: Training performant rl populations for combinatorial oplimization. Advances in Neurul Information Processing Systems, 36, 2024.
E.J. Gumbel. Statistioal theory of extreme values and some practical applications: a series of lectures, volume 33. US Government Printing Office, 1954.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement. learning that matters. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In In- ternational Conference on Learning Represenlations, 2020. URL https:// http://ppwaaeeeeeeeeeeecooorrtaa mtt//rrr
André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. 24th European Conference on Artificial Intelliencce (ECAI 2020), 2020.
André Hottung, Bhanu Bhandari, and Kevin Tierney. Learning a latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2020.
André Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization prob- lems. In International Conference on Learning Representations, 2022. URL https://qpenreviee wew.:nnnntfofffieee..
n05caZwFwYu.
Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. Large language models can self-improve. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
URL httpa////pprrreeeeeeeeeeooommam
L.A.M. Huijben, W. Kool, M.B. Paulus, and R.J.G. van Sloun. A review of the gumbel-max trick and its extensions for discrete stochasticity in machine learning. IEEE PAMI, (113):133--177) 2022.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXim: 191060000.727 2019.
Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. arXiv preprint orXiv:2006.070:: 2020.
Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve up-hard routing problems. Advances in Neural Information Processing Systems, 34:10418-1000 10430, 2021.
15

---

Published in Transactions on Machine Learning Research (06/2024)
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neural combinatorial oplimization. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyu Cho (eds.), Advonces in Neurul Information Processing Systems, 2022. URL https:://ppnnrevie http:ppaaweeeeeeeeeeeeorrreeniie .att:/forumm/.ccellt221111..
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1226614 2014.
W. Kool, H. van Hoof, and M. Welling. Buy 4 reinforce samples, get a baseline for free! In International Conference Learning Representations, 2019a.
W. Kool, H. van Hoof, and M. Welling, Estimating gradients for discrete random variables by sampling without replacement. In International Conference on Learning Representations, 2020.
Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference on Learning Represenlations, 2019b. URL https://opennrevier http::///ppppueeeseaaaaa//aatttt aataaa
Wouter Kool, Herke Van Hoof, and Max Welling, Stochastic beams and where to find them: The gumbel-top-k trick for sampling sequences without replacement. In International Conference on Machine Learning, pp. 3499-3508. PMLR, 2019c.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. In International conference on integration of constraint programming, artificial intelligence, and operations research, pp- 190 213. Springer, 2022.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21188 21198, 2020.
Gilbert Laporte. The vehicle routing problem: An overview of exact and approximate algorithms. European journal of operational research, 59(3):345 358, 1992.
J. Li, W. Monroe, and D. Jurafsky, A simple, fast diverse decoding algorithm for neural generation. arXiv preprint 1rXx::611.0066. 2016.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Thirly-seennth Conference on Newral Information Processing Systems, 2023.
Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances in Newral Information Processing Systems, 34:11096 11107, 2021.
Chris Maddison, Daniel Tarlow, and Tom Minka. A sampling. Advances in neural information processing systems, 27, 2014.
Gita Naseri and Mattheos AG Koffas. Application of combinatorial optimization strategies in synthetic biology. Nature communications, 11(1):2446, 2020.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
Yazhe Niu, Yuan Pu, Zhenjie Yang, Xueyan Li, Tong Zhou, Jiyuan Ren, Shuai Hu, Hongsheng Li, and Yu Liu. Lightzero: A unified benchmark for monte carlo tree search in general sequential decision scenarios. In Thärty- seventh Conference on Neural Information Processing Systems Dalasels and Benchmarks Track, 2023. URL attps://openrevievv.nu http://www..eetoooo///d/tdddd//e
Junyoung Park, Jachyeong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59(11)33360 3377, 2021.
Junyoung Park, Sanzhar Bakhtiyarov, and Jinkyoo Park. Schedulenet: Learn to solve multi-agent scheduling problems with reinforcement learning, 2022. URL https://openrrviiee http:pparrrrreeee..eee/eaaaaaaaa nett/forumiid-nnikkdjjyuuy
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-perforuance deep learning library. Advances in neural information processing systems, 32, 2019.
16

---

Published in Transactions on Machine Learning Research (06/2024)
Laurent Perron and Vincent Furnon. Or-tools, google. OR-Tools. 9.3 ed: Google, 2022.
Jonathan Pirnay, Quirin Göttl, Jakob Burger, and Dominik Gerhard Grimm. Policy-based self-competition for planning problems. In The Bleventh International Conference Learning Representations, 2023. URL https:
//apenreview wtwp://orummiiiSSSfiiooo000
Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables imput length extrapolation. In International Conference on Learning Representations, 2022. URL httpps//openreviee net/ forumPPddRR3d@PpO000.
S.J. Rennie, E. Marcheret, Y. Mroueh, J. Ross, and V. Goel. Self-critical sequence training for image captioning. IEEE CVPR, 2017.
Reuven Rubinstein. The cross-entropy method for combinatorial and continuous optimization. Methodology and computing in applied probability, 1:127-190, 1999.
Abdelkader Sbihi and Richard Eglese. Combinatorial optimization and green logistics. Annals of Operations Research, 175:159 175, 2010.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. XrXiv preprint orXio: 1rXi:11777.6347 2017.
Kensen Shi, David Bieber, and Charles Sutton. Incremental sampling without replacement for sequence models. In International Conference on Machine Learning, pp. 8785-8795. PMLR, 2020.
E. Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64:278-285, 2857, 1993.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Natalia Vesselinova, Rebecca Steinert, Daniel Perez-Ramine and Magnus Boman. Learning combinatorial optimization on graphs: A survey with applications networking. JEEE Access, 8:120388 120416, 2020.
Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neighborhood. Computers & Operations Research, 140:105643, 2022.
Vieira. Gumbel-max trick and weighted reservoir sampling. http://timoleiiraggihiie http:/httt...////////////////// 01/gumbel-max trick- and- weighted-reserooll sampling// 2014.
Vijayakumar, M. Cogswell, R. Selvaraju, Q. Sun, S. Tee, D. Crandall, and Batra. Diverse beam search for improved description of complex scenes. AAAI, 2018.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Aduances neural information processing systems, 28, 2015.
R.J. Williams. Simple statistical learning, 8:229 256, 1992.
algorithms for connectionist reinforcement learning. Machine
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristies for solving routing problems. IEEE transoctions on neural networks and learning systems, 33(9):5057-5069, 2021.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 12049, 2021.
Xin-She Yang.
Nature-inspired metaheuristic algorithms. Luniver press, 2010.
J.I. Yellott Jr. The relationship between luce's choice axiom, Ulurstone's theory of comparative judgment, and the double exponential distribution. Journal of Mathematioal Psychology, 15(2):109-144 1977.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learaing to dispatch for job shop scheduling via deep reinforcement learning, Advances in Neural Information Processing Systems, 33:1621-168 2020.
17

---

Published in Transactions on Machine Learning Research (06/2024)
Cong Zhang, Zhiguang Cao, Wen Song, Yaoxin Wu, and Jie Zhang. Deep reinforcement learning guided improvement heuristic for job shop scheduling, In The Twefihh International Conference on Learning Representations, 2024. URL https://openneevie net//orruniidejssaarrtt
Linlin Zhao, Weiming Shen, Chunjiang Zhang, and Kunkun Peng. An end-to-end deep reinforcement learning approach for job shop scheduling. In 2022 IEEE 25th International Conference on Computer Supported Cooperatioe Work in Design (CSCWD), pp. 846, 2022, doi: D0.100//CCCWD552222222277776
18

---

Published in Transactions on Machine Learning Research (06/2024)
A Background on Stochastic Beam Search
This scction briefly describes the Gumbel-Top-k trick and the essence of Stochastic Beoms and Where to Pind Them (Kool el al., 2019c).
A.1 The Gumbel-Top. Top-k Trick
We denote by Gumbel(u) a Gumbel distribution with location μ E R and unit scale. The distribution Gumbel(0) is the standard Gumbel distribution. Similarly to Kool et al. (2019c); Huijben et al. (2022), we write Gp for random variable following Gumbel(p)), and omit μ in the subseript in the case of standard location μ 0. The Gumbel distribution is closed under scaling and shifting, in particular for standard G (0 we have μ + G ~ Gumbel(u).
Gumbel-Max and Gumbel-Toppk trick The following is a condensed summary of the preliminaries in Kool et al. (2019c), with attribution to Gumbel (1954); Yellott Jr. (1977); Maddison et al. (2014); Vieira (2014). Consider a discrete distribution Categorical((i,... ,Px) with K categories and the probability pt of the i-th category. Let &e be unnormalized log- pee-robabiilties (logits) for p,, ie., & exp oz. We can obtain a sample from this distribution by perturbing each logit with a standard Gumbel and choosing the largest element ('Gumbel-Mar trick'): : Let Gø, = o, + G3 with G, ~ Gumbel(O), then Go, ~ Gumbel(0:: by the shifting property and arg max; Gø M.
In general, for any subset. B (I,..., K} have
max Gø. Gumbel rEB
log Σ cxp (Φt) and jEB
(7)
exp (di)
arg max Go. ~ Categorical
ΣJEB exp (0,) E
(8)
VEB
with max and arg max being independent.
The Gumbel-Max trick can be generalized to drawing an ordered sample (ii...., it) without replacement of size k "Gumbel-Topx trick') by finding the indices of the top l perturbed logits (denoted by arg top k):
= arg top k G
A.2 Drawing Samples Without Replacement from a Sequence Model
Beam search Beam search is a low-memory, breadth-first tree search of limited beam width k. Given a policy n, the initial beam of a search from root node (i.e., an empty sequence) with beam width consists of the top & first tokens, ranked by their tog-probability. Iteratively, at step t, each partial sequence in the beam expands its k most probable tokens. The resulting expanded beam is again pruned down to k by taking the top k partial sequences according their total log- probabbbaillsies log (ag(((1.) Σt= log ( (1ra-1), where a1 is any sequence in the expanded beam. Depending on the underlying factorized model, the final sequences found by beam search are often generic and lack variability (Vijayakurnar et al., 2018).
Stochastic Beam Scarch In Stochastic Beams and Where to Find Them (Kool et al., 2019c). Kool et al. apply the Gumbel-Top-k trick in an elegant way to sample sequences without replacement from a sequence (i) model. Assuming that the full true is instantiated with all possible complete (Icaf) sequences a with NJ, one would sample distinct sequences with the Gumbel-Top-k trick by simply considering the perturbed log probabilities G Gumbel(o,), where Φ; = log T (+)). Of course, instantiating the full tree is computationally infeasible practice. Instead, Kool et al. make the following crucial observation: Identify
node in the trie by the set S of leaves in its corresponding subtree and denote the corresponding (partial)
19

---

Published in Transactions on Machine Learning Research (06/2024)
sequence by a with ds log T7 ( Then
max Go. Gumbel
log JES
exp Uj Gumbel
Σm (1)
Gumbel (Øs).
(9)
jES
ie., the maximum of the perturbed log probabilities of the leaf nodes in the subtrec of S follows a Gumbel distribution with location log (aa)). Thus, instead of instantiating the full tree to sample k sequences, we can equivalently sample top-down (Maddison et al., 2014) and perform a beam search of width & over the perturbed log- ong-probabilitis by recursively propagating the Gumbel noise down the subtrce according to (9): Let a be any partial sequence in the beam at any step of the beam search with perturbed log bog-pobbaiiltyy Gos (which we can set to zero for the root node). Then we sample Gog for all direct children S' Children(S) under the condition that m Gég: Gog, and use Gøg as the scores for the beam search. We refer to the original paper by Kool et al. (2019c) for how to sample set of Gumbels with certain maximum.
Kool et al. (2019c) show on various language models that this simple procodure yields more diverse beam search results without sacrificing quality. From a sampling perspective, SBS can be seen as a principled way to randomize a beam search and construct stable unbiased estimators from a small number of sequences (Kool et al., 2019a; 2020).
B Policy Improvement Operation
We give a proof for the policy improvement obtained by Equation (1). The following lemma part of the policy improvement proof for the updated action selection of Gumbel AlphaZero based on Q-value completion (Danihelka et al., 2022). For coherence, we formulate and prove it in our general setting, with attribution to Danihelka et al. (2022).
Lemma: Consider a categorical distribution over the domain Ω = fl...., n) with corresponding probabilities (1) for E Ω. Consider a map q: - IR, and let j Q. Let n' be the distribution obtained from æ by changing the unnormalized log- Dog-probability ('logit') of to
logit T'()) == log (() + +G() Exon [g(i)]
(10)
Then, Enery [g(i)] 2 E,-, [a))
Proof: We need to show that
(+)((())> 2 Σ (1))((1)
(11)
iE
SE
Let y = [q))]. xf) = 1, then y = 0, so मL π and the claim is true. Hence, assume that क = < Note that for any i i 22 {j}, we have ri) (1) with constant c= (EreRtor m()) + exp(v)r(j) -1
As Eierrn T(1) = xjj), we can rewrite E [g())] as
x())((i) Σ EKeR ((k)
E [a(i)] = = + Σ +(i)(1) = 1 + (1 (1- Σ
(12)
kE
(EM(i))
+ (1
(13)
- - +
(14)
Analogously, get
en (i)g(t)
E (a(1)) nt x'(((()) (1- +()) Σ
(15)
Ekemrot CT (k)g(k)
(E
- -
(16)
20

---

Published in Transactions on Machine Learning Research (06/2024)
the constant cancels out. In particular, equivalently to (11), can show that
x'(i(a(i) 7) 2 =(i)((()) Q)-
(17)
By the policy update, we have x') > =(i) = y > 0, so (17) follows if we can show that y >>> 0 =
(d()) ④) > 0. But this is true, as
> 0 + (()) > Riva [a(i)]
+ q() > +()+())++++ + -1- (1- > m())
(18)
(19)
(20)
- - O.
(21)
We can now prove the policy improvement over the entire sequence model.
Let a be a policy, a > 0 and let a1. = (ai...., .r) be a full sequence drawn from x. Let be the policy obtained from æ by changing the logit of nt (ailana-1) for all i (T,...,T)
Proposition:
logit n' ra (q]/a::1)) == log IT
(22)
o (Baignaa()ann) [fa(a)r)] - Bet. [fa(
Then,
Ea (anrr)) 2 Eairos [f=(a1:))
(23)
We omit x in the subscript of f to simplify the notation. As only changes the magnitude of the step, we can assume without loss of generality that a = 1. We show the claim by induction on the length T.
Proof:
For T= = 1, we have air = (a1), and the update roduces to
logit n r'(a1) = log r(b) + f(a1) - EN'NT [f(a')]
(24)
Hence, the claim follows from the lemma above.
For the induction step for arbitrary T, we have
Eaiynn oo [[(ir))] = Σ (d(r)))(dd
(25)
d'ir
Σ n' (a' )aa ( [f(a]r)
(26)
Σ n (d.) (1)) (a(r))
(27)
where the last inequality follows from the induction hypothesis. But then, due to the form of the policy update (22), the lemma above can be applied again and we get
Σ Ed [f(a(rr)) (f 2 Σ
Eai ( [f(a(er)]
(28)
a
Σ ((aa.r))
(29)
ai
Eaj (((
(30)
what wanted to show.
21

---

Published in Transactions on Machine Learning Research (06/2024)
1S7 100. intermed mode: gresdy 4.00%
groudy
sweddy
CVRP N- 100, lace motel, gready 3.27%
0.7
50 it -2-3
50 S4-
1060
3.30
4.
3.825
Treely k21
04
44
touues
Sande
Narioar
JSSP 15. intemmslitte mode. groddy 15
150P 15x 15, late model
1527 20 20, Marmeciste midel greedy 14.15%
20.2 ale model greedy 10 100S%
5.
12.5
123
Namber ouund
Namber 1o
Figure 4: Comparison of the practical policy update (6) "GD' with the theoretical update (1) Theory GD' across various model checkpoints and beam widths & E {16, 32, 64). For TSP and CVRP, each data point corresponds to the average best solution across 100 instances. For JSSP, we evaluate the Taillard instances of the corresponding size. Nucleus sampling is switched off. Sampling for each data point is repeated 10 times; shades denote standard errors.
C Extended Experimental Results
C.1 Comparison with Theoretical Policy Improvement
We compare the practical policy update ('GD') that we use in our method (6) with the policy update (1) that yields theoretical policy improvement ('Theory GD'). The difference between them is that GD updates the logits in trajectory according to a single 'global' advantage. This global advantage is the difference between the outcome of the trajectory and the estimated expected outcome of the full policy, and it is propagated recursively to all ancestors of the corresponding leaf node. In contrast, Theory GD updates the logit of each ancestor individually by computing the difference 'locally' between the expected outcome of a node and its direct parent. While Theory GD yields a provable policy improvement, there are two practical difficulties: i.) In GD, we only need to compute single expected value. For Theory GD, we must compute the expected value for each encountered node individually. ii.) In GD, can use all k sampled trajectories to compute the expected outcome of the full policy, For Theory GD, when computing the advantage of particular node, we need to estimate the expectation of the node and its parent. In particular, we can only get a non-zero advantage if there are at least two trajectories through the parent.. Depending on the confidence of the model and the beam width k, this is often not the case for nodes deeper in the tree.
In Figure 4 we compare Theory GD with our chosen practical update GD over different checkpoints and beam width & E (16, 32, 64) as in Section 5.3. We use the same values for a in training, but do not apply nucleus sampling. GD and Theory GD perform similarly on the TSP, where the model is confident early While Theory GD is still a strong update method the CVRP and JSSP, GD outperforms it in almost all cases. Coupled with the fact that GD only needs to compute single expected value and is easier to implement, we consider it more advantageous for neural CO. However, in many cases, the results are close, which illustrates the theoretical rationale for GD.
C.2 Comparison with Self-Improving Training Method for LEHD on TSP
Concurrently to Drakulic et al. (2023), Luo et al. (2023) propose the 'Light Encoder Heavy Decoder' (LEHD) model for routing problems and also show promising generalization capabilities. The structure of LEHD is similar to BQ: however, while BQ only shares an affine embedding of the nodes across all time steps, LEHD encodes the nodes with single attention layer. The decoder consists of six attention layers, and in BQ,
22

---

Published in Transactions on Machine Learning Research (06/2024)
Table 3: Optimality gaps for TSP compared with LEHD with and without labeled data. For LEHD RL+RRC+SL, we take the results from the original paper, which are better than the ones we obtained with our implementation.
Method
Test
Generalization
TSP N 100
TSP N 200
TSP N 500
TSP N = 1000
LEHD SL, greedy
0.58%
0.95%
1.72%
3.34%
LEHD RL+RRC+SL, greedy
1.07%
1.45%
2.56%
4.52%
LEHD SI GD (ours), greedy
0.40%
0.72%
1.43%
3.30%
Table 4: Inference with Gumbeldore on the CVRP. For N 100, we only consider a test subset of 1000 instances. SBS and GD results are averaged over five repetitions. We use nucleus sampling with constant. p 0.8 for SBS and GD, and keep 3.0 for GD.
Method
Test
Generalization
N = 100
N = 200
N 500
N 1000
Gap
Gap
Gap
Gap
Beam 128
1.16%
1.10%
1.72%
4.28%
Beam 256
1.00%
0.97%
1.60%
4.27%
Beam 512
0.86%
0.90%
1.40%
3.85%
SBS 32 x 4
0.80%
1.07%
2.44%
6.04%
SBS 32 8
0.65%
0.87%
2.34%
6.00%
SBS 64 8
0.51%
0.73%
2.20%
5.80%
GD 32 4
0.73%
1.03%
2.13%
5.25%
GD 32 8
0.59%
0.76%
2.03%
5.12%
GD 64 8
0.49%
0.56%
1.88%
4.76%
the model is trained to predict the next node of random subtours sampled from expert solutions. Luo et al. (2023) additionally present a training process on TSP that does not require solutions from solvers as follows:
Train LEHD on TSP N 20 with self-critical REINFORCE for some time.
Generate a training set of 200,000 random instances of TSP N 100 and generate solutions for them with the current model.
Sample subtours for each instance and randomly reconstruct (RRC) them to improve the solutions.
Continue training of LEHD by supervised learning with the generated dataset.
In Table 3, we compare this approach (LEHD RL+RRC+SL) to their supervised approach and our method. We see that our simple training process based on sampling surpasses the relatively complicated RI. + randomly roconstructed solutions approach and obtains results comparable to its supervisod counterpart.
C.3 Gumbeldore at Inference Time
There is a plcthora of work on how to exploit an alrcady trained policy for neural CO, such as Simulation- Guided Beam Search (Choo el al., 2022) or (Efficient) Active Search (Bello el al., 2016; Hot lont et al., 2022) (cf. Section 2). Although we consider our sampling method mainly for training, this section, we evaluate the performance during inference in the low sample regime. High exploration plays a subordinate role this setting, so we use Top-p sampling with constant p in all rounds. Table shows inference results using the model trained with SI GD. We compare GD k with rounds and beam width with sampling without.
23

---

Published in Transactions on Machine Learning Research (06/2024)
Table 5: Inference with Gumbeldore on the JSSP. Results are averaged over five repetitions. all cases, we use nucleus sampling with constant p 0.8, and keep o 0.05 for GD.
15 x 15
20 x 15
20 x 20
30 x 15
30 X 20
50 X 15
50 x 20
100 x 20
Method
Gap
Gap
Gap
Gap
Gap
Gap
Gap
Gap
SBS 32 4
5.0%
5.7%
7.3%
6.1%
9.4%
1.1%
4.3%
0.4%
SBS 32 x 8
4.7%
5.3%
7.0%
5.7%
9.0%
0.9%
4.0%
0.3%
SBS 64 x 8
4.3%
5.3%
6.4%
5.2%
8.8%
0.9%
4.0%
0.3%
GD 32 x 4
4.8%
5.6%
7.0%
5.8%
9.2%
1.1%
4.3%
0.4%
GD 32 8
4.5%
5.3%
6.7%
5.3%
8.8%
0.9%
4.0%
0.3%
GD 8
1.2%
1.8%
6.3%
5.0%
8.6%
0.8%
3.7%
0.2%
replacement (with Top-p) via round-based SBS & x and to beam search with corrosponding beam width. We see that both sampling methods outperform beam search on N = 100 and N = 200 but not on N = 500 and N = 1000. Furthermore, the policy update of GD leads to a consistent improvement over SBS. The CVRP results indicate that combining GD and deterministic beam search could result a robust inference method. On the JSSP in Table 5, we observe the same improvement of GD over SBS. The margin, however, is not as wide for intermediate models by Section 5.3. We omit the results for deterministic beam search JSSP, as SBS supersedes them with nucleus sampling and beamn width of 16 (cf. Table 2).
C.4 Gomoku: A Toy Problem
Played on a Go board, Gomoku is a game for two players who take turns placing their stones on the board, starting with black. The first player to have five stones a row horizontally, vertically, or diagonally wins. We formulate the following problem: Given a deterministic expert bot playing black, how long does take a greedy model playing white learn from scratch to beat the opponent from all possible starting positions of black? Here, the model's policy takes board configuration and predicts distribution over the next possible moves. We lake the deterministic rule-based bot ('vl'), the Gomoku state representation, and the AlphaZero architecture for Go provided by the LightZero benchmark suite (Niu et al., 2023). In each epoch, we generate training data by sampling multiple trajectorics using the current policy from all possible starting positions of black. Then, for each start position, we take from the sampled trajectories either random trajectory where white wins or, if there is no win for white, a random trajectory where black wins. In the case of a draw, we take random draw. The supervised training in each epoch then consists of learning the policy predict the next move of the winner. After each epoch, we greedily unroll the policy for each starting position of black and count the number of times white wins. How many epochs does il lake for white to win every lime? The formulated problem is not standard, and board games are usually approached with self-play. Therefore, it is instead a tiny illustrative toy problem to further show the applicability of our method.
We play on
9 Go board. First, we let the model sample 320 sequences with replacement for each possible starting position and train the policy in cach epoch on 100 batches of 32 pairs of the form (<board configuration>, <next move of winner>).. Repeated ten times, the model takes an average of 60.2 epochs for white to consistently beat black.
For training with GD, we score a complete trajectory with its game result: 1 for white win, -1 for a black win, and for a draw. We also sample 320 sequences in 10 rounds with an SBS batch size of 32. We completely turn off nucleus sampling and use the game outcome as an advantage to propagate up the tree (cquivalent to sctting the expected outcome a draw). Using a step size of 5, which heavily favors moves that lead to a win and punishing moves that lead lose, it takes an average of 47.7 epochs (~ 20% faster than sampling with replacement) for white to greedily win all the time.
24

---

Published in Transactions on Machine Learning Research (06/2024)
D Implementation and Experimental Details
Hardware and frameworks Our code is developed in PyToorch (Paszke al., 2019). Training and inference are performed for all experiments using two NVIDIA RTX A5000 with 24GB memory. As do not need to collect gradients during sampling, we can easily parallelize solution sampling for different instances in cach epoch. We spread it across 16 workers using ray.io.
D.1 Choice of Gumbeldore Step Size
We generally choose the slep size for the update in (6) follows: We train the model using round-based SBS (i.e., with 0) for 20 epochs with four rounds of beam width 32. We then perform grid search over E [0, 5] on small validation set.
D.2 Traveling Salesman Problem
D.2.1 Problem Setup
In the Euclidean TSP with N nodes in the unit square [0, 1J2 C R², node permutation (i.e., complete roundtrip, where all nodes are visited only once) with minimal edge weight should be found. A problem instance is defined by the two-dimensional coordinates of the N nodes. The sequential problem asks for choosing one unvisited node at a time. The objective function to maximize evaluates a full tour by the negative lour length. Random instances are generated in the standard way of Kool et al. (2019b) by sampling the coordinates of the N nodes uniformly from the unit square.
D.2.2 Policy Network
We use the transformer- baaseedreer-based architecture of BQ (Drakulic et al., 2023) and give short overview of the network flow: At the start, the coordinates of the N nodes (.1...., ) E R are affinely embedded into a latent space of dimension d, and we obtain nodes (z',..., ) E Nxd At each time step, given a partial tour with an origin node z and a destination node x', we add learnable lookup embedding to xf and z' and send them together with all unvisited nodes through a stack transformer layers. ReZero (Bachlechner et al., 2021) normalization used instcad of layer normalization within the transformer layers. No positional encoding is used, as the order of nodes does not play role. After the transformer layers, a linear layer Rd + R projects the processed nodes to logit vector in RN, from which the logits corresponding to x; and n', are masked out.
Trajectory prediction Given an instance of N nodes, choose random node as the origin, mark it visited, and set it as the destination node as well. The network predicts distribution over the remaining nodes, and after choosing one, we mark this one as visited, set it as the new origin node, and so on.
We use a latent dimension of = 128 (following a preprint version of BQ) and nine transformer layers with eight heads and feed-forward dimension of 512.
D.2.3 Supervised Training
Subtours Given instance and complete tour, train random subtours. That is, given E (4...., NY (a sublour with three nodes is trivial) and an instance of size N = 100 with a complete lour, we sample a subtour of length t. The first and last nodes of the subtour are taken the origin and destination nodes, and the corresponding target to predict is the next node after the origin node. For computational efficiency, we keep fixed within the same minibatch.
Subtour augmentation During training, we randomly augment each sampled subtour in the following ways, each of which does not change the solution:
Switch the direction of the subtour
25

---

Published in Transactions on Machine Learning Research (06/2024)
Swap and y coordinates for each node
Reflect all nodes along the horizontal line going through the center (0.5, 0.5)
Reflect all nodes along the vertical line going through the center (0.5, 0.5)
Rotate all nodes around the center (0.5, 0.5) by a random angle. Note that this can lead to coordinates outside [0, 1]2. In this case, we linearly scale the coordinates so that they lie within the unit square again.
Hyperparameters In each epoch, we train on 1,000 batches consisting of 1,024 sampled subtours. We use Adam (Kingma & Ba, 2014) as an optimizer, with an initial learning rate of 1c-4 and no decay. Gradients are clipped to unit Lo-norm.
D.2.4 Gumbeldore Training
In each epoch, we sample 1,000 random instances for which we sample 128 solutions with GD using a beam width of k = 32 in n = rounds. We use a step size of a = 0.3 throughout training. We start with Puin = (i.e.; no nucleus sampling) to not restrict exploration in any way, and set Pmin = 0.95 after 500 epochs. Supervised training performed with the best sampled solutions as in its supervised counterpart; however, use an initial learning rate of 2c-4. To better utilize the GPUs, we parallelize the sampling procedure across 16 workers which share the two GPUs. Sampling all solutions for the 1,000 instances takes about one minute for N = 100.
D.3
Capacitated Vehicle Routing Problem
D.3.1 Problem Setup
A CVRP problem instance is given by coordinates of N customer nodes and one depot node. Each customer node æ; has a demand 6,, which must be fulfilled by delivery vehicle of capacity D. The vehicle must visit all nodes exactly once in customers' demands visited in subtour does not exceed the vehicle's capacity D. The goal is to find set of subtours with minimal total distance that visits all customers.
of subtours that start and end at the depot node, and where the sum of the
Instance generation Following (Kool et al., 2019b; Drakulic et al., 2023; Luo et al., 2023), instance is generated by sampling the coordinates for the customers and the depot uniformly from the unit square. The demands 8 are sampled uniformly from the set 11,...,9}, The vehicle capacity is set respectively to = 50, 80, 100, 250 for corresponding = 100, 200, 500, 1000. We normalize the vehicle's total capacity to Î and the demands to 8,
Solution formation To align solutions, we also follow the approach of (Kool et al., 2019b; Drakulic et al., 2023; Luo et al., 2023) and describe complete solution by two vectors, where customer indices, and the other is binary vector indicating whether the i-th customer in the permutation is reached via the depot or not. For example, a complete tour (0, 1, 4, 5, 0, 2, 3, 0, 6, 7, 0), where index 0 denotes the depot, consists of 3 subtours which start and end at the depot. The corresponding solution split into the two vectors of length 8 is 3, 6, 7,8) 8) for the permutation and (1, 0, 1, 0, 1,0,
is permutation of the
D.3.2 Policy Network
As for the TSP, use the transformer- bassedddde-e-ddddddd architecture of BQ (Drakulic et al., 2023) and give short overview of the network flow: At any point in time, we represent each node (including the depot) as a four-dimensional vector, where the first two entries are the coordinates of the node, the third entry is the demand (with 0 demand for depot) and the last entry is the current remaining capacity of the vehicle. Also, at any point, we have an origin node (oqual to the depot the remaining unvisited nodes are affinely embedded into the latent space Rd, and we mark the origin and the depot by adding learnable lookup embedding as for the TSP. The stack of transformer layers processes
the beginning). The depot, the origin node, and
26

---

Published in Transactions on Machine Learning Research (06/2024)
the embeddings of the depot, origin, and remaining nodes before projecting the output to two logits for each remaining node via linear layer. The two logits correspond to choosing the node via the depot or directly from the origin. We mask all infeasible actions, indicating whether a node must be reached via the depot as its demand exceeds the current capacity of the vehicle (or must be reached via the depot as the origin is equal to the depot). The structure of the attention layers is identical the ones in the TSP.
As in the original paper (Drakulic et al., 2023), we use a latent dimension of 192, nine transformer layers with 12 heads, and feed-forward dimension of 512.
D.3.3 Supervised Training
Subtours As for the TSP, we train on random subtours. We impose the restriction that sampled subtour must end at the depot (Luo et al., 2023).
Subtour augmentation We augment an instance by randomly reversing the direction of individual subtours. We then sort the subtours in ascending order by the remaining vehicle capacity at the end of the subtour. Sorting the subtours is a crucial step that we copy from Drakulic et al. (2023), who analyze that the order of the subtours has a substantial impact on the final performance of the model, where the model obtains better results when learning to schedule subtours first which utilize the vehicle as good as possible. Finally, we perform the same random geometric augmentation techniques as for TSP (reflection, rotation, flipping).
Inference
During inference, we follow the approach of Drakulic et al. (2023) and consider at each step the 250 nearest neighbors of the current origin node.
Hyperparameters
The hyperparameters for training are identical TSP.
D.3.4 Gumbeldore Training
Gumbeldore hyperparameters are identical to TSP, with a step size of a = 3.0. To enhance generalization, we sample the vehicle capacity from (40, (10,41,..... 100} during instance generation.
D.4 Job Shop Scheduling Problem
D.4.1 Problem Setup
Problem definition We use a similar notation as in Pirnay el al. (2023). In a JSSP instance of size J x M, we are given J jobs. Each job consists of M operations which need to be scheduled on M machines. There is a bijection between the operations of job and the set of the machines, i.e., every job must visit each machine exactly once. Thus, job E [I,.....} can be represented by (or,1 P where o,1 E (1,..., M) is the index of the machine on which the 1-th operation must run, and Pt, E R2 is the processing time that it takes to process the operation on machine oi, The operations of job must run in order; only one operation can be processed by a machine at time, and once an operation starts, it must finish. The aim is find schedule with minimum makespan, where the makespan is given by the time the last machine finishes. In particular, the objective function to maximize is defined by the negative makospan of a schedule. A JSSP instance is fully defined by the set
Instance generation We generate a random instance in the way of Taillard (1993) by uniformly sampling processing times from {l,..., . (.....99])..... and setting the order of the machines on which job must run as a uniformly random permutation of the set of machines.
Schedule representation As there is bijection between the operations of job and the M machines, and the operations must run in order, we can represent a schedule by an ordered sequence of job indices (j.M)...j.M) where ji E J.. Here, the occurrence of a job means that the next unscheduled operation of job should be processed on the corresponding machine as soon as possible. Note that, as in the routing problems, sequence defining a schedule is generally not unique. In particular, in our constructive sequential formulation, we choose unfinished job index after another until all jobs are finished.
27

---

Published in Transactions on Machine Learning Research (06/2024)
Job idx
Proc. time
Machine Scheduled idx
Job
Job
2
3
2
Yes
Machine
Current schedule:
Yes
2
(L. 2,
4
3
No
Machine
machh
(3,3,0,13
4
(7, 12)
3
Yes
Machine
1
7
3
No
Machine
1
Processing
Figure 5: Example of a problem instance with 2 and A 4. The operations' processing times and machines are shown in the table on the left. The first two operations have alrcady been scheduled with the partial schedule (1, 1, 2, 2). The corresponding Gantt chart and availability times are shown on the right.
Tail subproblems Similar the routing problems, we want to employ similar tail-recursion property. For this, let (t.)) ( V/ be problem instance. We introduce two additional tuples (Amaahh) MMM and (A) where Afrach indicates the availability of the i-th machine, i.e, the earliest time an operation can start on machine i. Analogously, A/ah indicates the earliest time the next operation of the i-th job can start. For an empty schedule, the availability times are all set to zero. When choosing job with index i, let / be the index of the operation that to be scheduled and m = o, be the index of the machine on which the operation must run. We then compute the finishing time 2 of the operation via
max Alob Amach } + Pi,
(31)
and update the availability times to
Amach
Ajob
2.
(32)
The crucial thing note here that given an optimal schedule ji--r) with minimal makespan and g E (1.....J- M), the subschedule (j..... is an optimal solution to the subproblem where after scheduling j1 Jq the corresponding operations have been erased, and the availability times have been updated according to (32). A small example can be seen in Figure 5
This properly motivates how our model is set up: For the routing problems, we have a heavy decoder that only cares about unvisited nodes and no longer about how visited previous nodes. Similarly, for the JSSP, we are only interested in the unscheduled operations and the availability times at any time, We feed this information to a network described below.
D.4.2 Policy Network
A suitable architecture for the JSSP should account for the fact that the problem is invariant to the job and the machine indexing (for the latter, it is only important if two operations must run on the same machine, but not which one). Our proposed architecture processes the J M operations with multiple transformer layers, and we use masking to account for the indexing invariance. We make this precise as follows:
Let mach Alob be the availability times at any constructive step. Let be the index of an unfinished job, and m, be the index of the machine on which the next unscheduled operation of job must run. Define Ti max Alo Amach) } the time at which this operation would start if it were scheduled next. We represent the state of the instance by A E /xxx2 where for i E {I....,J} and E (l,..., M) we set
Pi. Fi min (1......
A.i
(33)
100'
100
28

---

Published in Transactions on Machine Learning Research (06/2024)
Le., we repeat the start time across all operations for job, shift the time back to O, and scale the processing times into [0. We affinely embed A into a latent space Rdd to obtain A E RJxMxd, We compute a sinusoidal positional encoding P E M (Vaswani et al., 2017) which we add to each job i via A, + P. We send the resulting sequence of operations through a stack of pairs of transformer layers, wherein each pair:
1.) We use ReZero normalization (Bachlechner et al., 2021) as in the architecture for the routing problems.
ii.) In the first transformer layer, referred to as the 'job-wise layer':
Only operations within the same job attend to each other. In practice, this can be efficiently achieved by folding the job dimension into the batch dimension, i.e., reshaping the sequence from R 3xxxxxXxd to RB-Jxxxx,
We mask all operations that have already been scheduled.
We add ALiBi (Press et al., 2022) positional information to query-key attention scores as an attention bias in each head of job-wise layer. Precisely, let be the number of heads, then the ALii--poccifcc slope for the k-th head is given by the 2 * Then, we set the additive bias for a querying operation with index 4 E { M and a key operation with index l2 to 2 SA (12 - (1) for the k-th head. While not strictly necessary for good performance, we found that ALiBi slightly improves the results by carrying the positional information of the operations through all job-wise layers.
iii.) In the second transformer layer, referred to as the 'machine-wise layer':
We let two operations attend each other only if they need to run on the same machine.
We also mask all operations that have already been scheduled but do not employ ALiBi attention bias.
The operations transform according to different roles by repeatedly switching between job- and machine-wiss layers. Note that this strategy is invariant to the job and machine indexing. In principle, it is possible achieve a similar effect by only considering the entire sequence in R Bx for all transformer layers and using different masks within individual heads to account for job-wise and machine-wise altention. We set tled for the switching strategy, as folding the jobs into the batch dimension practically saves computation time,
After the transformer layers, we gather the output O E Jxd corresponding to the next unschoduled operation of each job (in case the job is already finished, we take the last operation ). We apply a final transformer block on the sequence O masking already finished jobs. Afterward, we project the output to logits with a linear layer Rd + R, again masking finished jobs.
Figure 6 gives an overview of the network.
Size We use a latent dimension of d= 64 with three pairs of transformer layers, where each layer has eight heads and a feedforward dimension of 256. With the final transformer layer, this amounts a total of layers.
D.4.3 Gumbeldore Training
We train the model with GD for 100 epochs. In each epoch, we randomly pick a J x M size in {10 15, 15 x 15, 15 x 20). We generate 512 random instances of the chosen size for which sample 128 solutions with GD using a beam width of k = 32 in = 4 rounds. We use fixed advantage step size of a 0.05. We start with Punin = 1 and set Pmin = 0.95 after 50 epochs. During supervised training on the generated solutions, given a full trajectory (i,...-jj-M), we uniformly sample E (1....,J J. M - 1} and compute macc and Ajob according to the subschedule (g.1.. The training target is then to predict jq. No further augmentation is performed.
As for the routing problems, we use an initial learning rate of 2 and clip gradients to unit norm.
29

---

Published in Transactions on Machine Learning Research (06/2024)
Job-wise Transformer Layer
Machine-wiie Transformer Layer
Attention blas
Job
Maak
2
2
Hinf
Hin
HET
2
Key
3
3
Inf
int
4
Final transformer layer
jgb
4
Linear
loght jab
4
Key
3
Finf
in
4
2
3
3
2
Figure 6: Overview of the network architecture, using the two jobs with four operations from Figure 5. Boxes represent operations, and the numbers in the boxes indicate the machine on which has to run. Here, we assume that the first two operations of Job and the first operation of Job 2 are already scheduled. In the job-wise transformer layer, only operations within the same job attend each other. We mask scheduled operations. We accommodate masking and ALiBi positional information in the additive attention bias (shown before scaling with slope). In the machine-wise layer, only operations running the same machine may attend to each other, also masking scheduled operations (pink square: mask, green square: do not mask). The next possible operation is gathered for each job and used to predict the policy.
E
Comparison to Concurrent Work
Independently of our work, Corsini al. (2024) develop similar learning strategy for the JSSP. They also lurn away from RL and sample 256 solutions in each epoch for randomly generated instances using the current model. Then, they supervisedly train GNN Pointer Network on the generated solutions. They call this strategy 'self-labeling' While our Algorithm 1 is slightly different from theirs (maintaining best greedy policy and expanding the dataset in case of no improvement), their work and ours match in the spirit of applying behavior cloning to sampled solutions. However, Corsini et al. (2024) focus on the JSSP and their proposed GNN architecture using the disjunctive graph representation of the JSSP. Most importantly, while they discuss different sampling schemes, they settled on sampling with replacement (Monte Carlo i.i.d. sampling) from the sequence model, which they found sufficient for their approach. Our main contribution revolves around principled way to get the most out of few samples, applied to various neural CO problems, and we show in Section 5.3 that our method can significantly improve the sampling performance. Furthermore, compare our method on the JSSP with their approach in Table 2. Our work is also motivated by bridging the problem that large network architectures that generalize strongly can be computationally challenging to train with policy gradient mothods. However, we emphasize that we believe the work of Corsini et al. (2024) and ours are mutually reinforcing, as both conclude that a more 'straightforward" training stralegy than self-critical policy gradient methods can lead strong performance in neural CO.
30


Reviews:
[{"review_id": "genAEhlhIL", "reviewer": "Reviewer_67nt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Straightforward proposal to enhance self-improvement algorithm for combinatorial optimization.\n- Clearly and carefully prepared papers.\n- Results show good results on several combinatorial optimization benchmarks.\n\nWeaknesses:\n- Rather niche proposal for a specific algorithm. The interest for the approach might limited to a small community.\n- Number of baselines used for comparison seem low, and I am wondering whether these baselines are the best to be used.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper is proposing a new approach for sampling sequences in the context of neural combinatorial optimization. The approach consist in a method for sampling a variety of likely sequence without duplicates in the set -- which duplicated seems likely to be obtained by purely random sampling according to the model. This lead to improvement to the use of self-improvement algorithm with random sampling. The approach is evaluated on several combinatorial optimization benchmarks, with good performances compared to the other baselines compared.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Unfortunately, this paper is somehow outside my main expertise fields, I don't have specific technical changes requested to improve the paper. However, I find the paper to be somehow difficult to grasp at first for someone outside the neural combinatorial optimization field. I would like that the paper provide more background and help the reader to better understand the field, not assuming intimate knowledge with it. Also, the contribution make in the paper appears rather specific, for a niched algorithm, and as such of interest for a limited community. I would like the authors to develop more on that, and highlight well the contributions of the paper, For instance, it wasn't obvious to me whether the self-improvement neural combinatorial optimization presented in Algo. 1 is a proposal from some other paper or a novel proposal. The work is not very well contrasted with other work, for an outsider like me, the message is not very clear on the contributions and novelties.", "broader_impact_concerns": "I don't see specific broader impact concerns here, that more an algorithmic work aimed at improving combinatorial optimization.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "enOJNf28FV", "reviewer": "Reviewer_SCRr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The submission is well written with clear motivations. \n\nThe proposed method is novel by using some existing techniques is a well-designed manner. \n\nThe performance improvement of the proposed method is thoroughly demonstrated empirically.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission considers neural combinatorial optimization, where one uses neural-network-based methods for combinatorial optimization. \n\nThe proposed method is an improvement of classic behavior cloning (BC) methods. Specifically, the existing BC methods require lots of expert data, which can be hard to obtain, while the proposed method uses a novel sampling method to reduce the need of the expert data. \n\nExperiment results are provided supporting the performance improvement of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I find the submission well-written and self-contained. I do not have any specific suggestions on changes to the author.", "broader_impact_concerns": "I do not have such concerns for this submission.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "X60VXrSFBa", "reviewer": "Reviewer_WWT5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n* The paper proposed a new method for solving CO problems that lies at the intersection of supervised learning and reinforcement learning.\n* The paper provides detailed discussion of methodological details.\n* The experiments show scalability of the method and the importance of the proposed sampling method.\n\n**Weakness:**\n* I think the paper would benefit from showing some data on sample efficiency of the proposed method compared to other methods. This would help strengthen the claim of sample efficiency of the proposed method.\n* The paper could benefit from a (potentially brief) broader discussion of traditional CO approaches, such as genetic algorithms, and position their proposed method compared to those.\n* An ablation of a policy without a transformer based architecture could strengthen the claim for the importance of that choice.\n* The paper could provide greater clarity in captions of Table 1 and Table 2; e.g., providing definitions for N and outlining the main takeaways.\n* The paper could clarify how the sequence based data is processed by the proposed transformer architecture and define relevant hyperparameters for it.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new method for neural combinatorial optimization that trains a neural network policy based on samples from a sampling method proposed in the paper. The paper first introduces combinatorial optimization (CO), as well as past machine learning approaches for solving CO. The paper argues that past reinforcement learning based approaches can be challenging to train and then outline their approach for training a policy based on trajectories sampled as pseudo-expert trajectories. At the end of the introduction, the authors outline their contributions focusing on the approach, the sampling method and experiments on TSP, CVRP and JSSP.\n\nThe paper then outlines related work followed by a detailed description of the problem setup and the algorithm. Section 4 describes the main contribution of the paper, which focuses on sampling method that enables sampling without replacement, but with improvement.  Here the paper discusses stochastic beam search and incremental sampling without improvement, as well as their Gumbledore sampling method. Next the paper provides details on theoretical policy improved and a description of the policy update method outlining how the sampling methods are integrated into the main algorithms. Section 5 describes the CO problems for which the proposed method shows the ability to solve CO problems at both small and large scales. The analysis also includes a section on sampling method performance. The paper then concludes with a discussion on limitations and a conclusion.\n\nThe main contributions of the paper focus on:\n* Providing a new method for CO that trains a policy based on an iterative sampling approach that lies at the intersection of supervised learning and reinforcement learning.\n* Showing scalability for the proposed method on different CO problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Based on the weaknesses above, here are some requested changes:\n\n**Important**:\n* Provide evidence to strengthen the claim of sample efficiency for the proposed method.\n* Add a discussion and traditional CO approaches and how they compare to the proposed method.\n* More detailed table captions.\n\n**Nice to Have**:\n* Clarity on the transformer based architecture.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: **Summary:**
The paper addresses an interesting problem (combinatorial optimization, CO) with a modern and sophisticated approach. The idea of using a model's predictions for self-improvement has been proposed before, but its application to CO seems to be particularly fruitful. The general approach is to treat the solution to a CO problem as a sequence of actions and train a sequential predictor to assign high probability to (near-) optimal solution sequences. The innovation of the paper is to neither rely on expert data (imitate expert sequences) nor plain RL, but instead sample candidate solutions from the model, evaluate them, and retrain the model to increase the likelihood of the most successful samples. The paper presents a theoretically sound and efficient way to implement this idea with modern sequence models (transformers). This requires addressing two central problems:
 * The whole scheme depends on being able to efficiently sample "good" candidate solutions - the paper uses stochastic beam search (which has been proposed before in a different context) which allows for efficient (and parallelizable) batch-wise sampling *without replacement* from the model. This significantly improves the sample diversity without deteriorating sample quality, and thus allows for a structured exploration of a (partial) breadth-first search-tree.
 * The model needs to be bootstrapped on its own predictions - the paper presents a theoretically sound policy-improvement method for this and derives a practical version of it that can be combined well with stochastic beam search.
The method is evaluated on three classic CO problems: Travelling Salesman, Capacitated Vehicle Routing, and Job Shop Scheduling. Results highlight the efficiency and good performance of the method, which is further supported by comparisons against relevant baselines and gold-standard approaches.

**Verdict:**
The paper is very well written, and includes a great introduction to CO and the various standard approaches for a broad, non-expert audience. The innovations in the paper are well motivated and situated within the current literature, and the methodology is well-described. The method is theoretically sound, practical, uses modern techniques and sequence models, and works well empirically. While parts of the method have been discussed before in other context (bootstrapping for self-improvement, stochastic beam search, and parts of the policy improvement via Gumbel-top-k), the application to CO is novel and original, and putting together the individual parts of the method is non-trivial (and supported by ablations). All reviewers agree that the claims in the paper are supported by accurate, convincing and clear evidence, and that the work is interesting to TMLR's audience. I agree with their assessment and believe that the work is clearly ready and suitable for publication at TMLR. 

**Certification:**
The paper is perhaps the highest-quality work that I have AE'd (7 papers) or reviewed (7 papers) for TMLR so far. The paper is very well written, and thanks to the great introduction to CO, and the literature review it is well accessible for a broad, non-expert audience. The method itself is original and well put together - the theoretical analysis nicely supports the method and does not bloat the manuscript with vacuous maths. Empirical results demonstrate that the method performs very well, and include great comparisons against SOTA and related methods, and important ablations. The paper is certainly interesting for a CO audience, but I believe that the method itself could also be highly relevant (at least highly inspiring) for using transformers in more general planning and control problems where expert data is not available and plain RL is prohibitively slow (the setting in the paper should straightforwardly translate to open-loop control and planning, and may be suitable to be included in feedback control and sequential decision-making). I therefore propose to consider the paper for a 'Featured' certification.
Decision: Accept (poster)