Simulation-guided Beam Search for Neural Combinatorial Optimization
Authors: Jinho Choo
Yeong-Dae Kwon
Jihoon Kim
Jeongwoo Jae
André Hottung
Kevin Tierney
Youngjune Gwon
Venue: NeurIPS 2022 Accept (2022)
Keywords: Combinatorial Optimization
Reinforcement Learning
Active Search
Beam Search
MCTS
Tree Search
TSP
CVRP
Flow-Shop Scheduling

Abstract: Neural approaches for combinatorial optimization (CO) equip a learning mechanism to discover powerful heuristics for solving complex real-world problems. While neural approaches capable of high-quality solutions in a single shot are emerging, state-of-the-art approaches are often unable to take full advantage of the solving time available to them. In contrast, hand-crafted heuristics perform highly effective search well and exploit the computation time given to them, but contain heuristics that are difficult to adapt to a dataset being solved. With the goal of providing a powerful search procedure to neural CO approaches, we propose simulation-guided beam search (SGBS), which examines candidate solutions within a fixed-width tree search that both a neural net-learned policy and a simulation (rollout) identify as promising. We further hybridize SGBS with efficient active search (EAS), where SGBS enhances the quality of solutions backpropagated in EAS, and EAS improves the quality of the policy used in SGBS. We evaluate our methods on well-known CO benchmarks and show that SGBS significantly improves the quality of the solutions found under reasonable runtime assumptions.

Simulation-guided Beam Search for Neural Combinatorial Optimization
Jinho Choo*1 +1
Yeong-Dae Kwon
Jihoon Kim Jeongwoo Jae
André Hottung"
Kevin Tierney
Youngjune Gwon
'Samsung SDS, Korea
Bielefeld University, Germany
Abstract
Neural approaches for combinatorial optimization (CO) equip learning mech- anism to discover powerful heuristics for solving complex real-world problems. While neural approaches capable of high-quality solutions in single shot are emerging, state-of-the-ane approaches are often unable to take full advantage the solving time available them. In contrast, hand-crafted heuristics perform highly effective search well and exploit the computation time given to them, but contain heuristics that are difficult to adapt goal of providing a powerful search procedure to neural CO approaches, we pro- pose simulation-guien -uidded beam search (SGBS), which examines candidate solutions within a fixed-width tree search that both a neural net-lcarned policy and sim- ulation (rollout) identify as promising. We further hybridize SGBS with efficient active search (EAS) [.. where SGBS enhances the quality of solutions backprop- agated in EAS, and EAS improves the quality of the policy used in SGBS. We evaluate our methods well-known CO benchmarks and show that SGBS sig- nificantly improves the quality of the solutions found under reasonable runtime assumptions.
dataset being solved. With the
Introduction
Combinatorial optimization (CO) problems arise in wide variety of real-world settings in which finding high-quality solutions quickly is an important, challenging task. Efficient methods for solv- ing CO problems have attracted significant attention, and the literature now contains vastly different styles of solution approaches. The majority relies on deennddd tricks and insights. However, neural approaches have recently begun offer means for data-driven optimization. Through inforcement learning (RL), a deep neural net can automatically learn to generate heuristics that are customized specific context for given dataset, without the intervention of domain expert or the need for a pre-existing optimization approach 2
Using construction paradigm for neural CO methods, solutions CO problem can be built in a step-by-step manner following the policy calculated by the neural network. Previous work this area tends to focus on building good policy network model and bringing the quality of its solution generated in a single shot as close to the optimal as possible. However, research for an effective inference method for neural CO has been rare. An effective inference strategy to maximize the quality the solution found within a given time budget is just as important, because practitioners of many industrial CO tasks are generally willing wait even up multiple days to find high-quality solutions to their problems.
A well-known search strategy for neural construction methods is sample solutions from the out- put probability distributions calculated by the neural network (e.g., [3] While this has better
36th Conference on Neural Information Processing Systems (NcurIPS 2022).
"quual contribution. Address: jinho mithol2.chorl 22choo @ samsung.com, k.d.kwon @ samsung.com.

---

performance than single shot (greedy) solution construction, its lack of search guidance results in quickly diminishing improvements in solution quality. An alternative to sampling Monte- Carlo tree search (MCTS) [ 61. which completes partial solutions in the tree with rollouts. MCTS is re- source intensive, potentially requiring long run times due to a multitude of rollouts and the size of the search tree. Another popular search method is beam search, which is low-memory, heuristic version of tree search. Beam search only expands a constant number of nodes at any level of the tree search, and has been applied by several neural CO techniques 7 g 2 [0]. However, beam search is a greedy algorithm that blindly follows the prediction of the neural network, good or bad.
In this paper, we present simulation-guidee beam search" specifically for solving CO problems. SGBS performs rollouts for nodes identified as promising by the neural network, which acts as a recourse mechanism to rectify incorrect decisions by the network. Only a select number of nodes identified as promising by the rollouts are expanded, and this process repeats. The implementation of SGBS is straightforward, requiring very little modi- fication from the basic sampling inference algorithm of any existing neural CO algorithm. Moreover, it maintains the high throughput efficiency that is the hallmark of neural network based sampling, as there is no complicated backpropagation that would prohibit batch parallelization of the search.
beam search (SGBS), which combines MCTS with
SGBS can be further partnered with efficient active search (EAS) M to achieve even better per- formance over longer time spans. EAS updates a small subset of model parameters test time to "guide" the sampling towards promising regions of the search space. SGBS and EAS have a syn- ergistic relationship when being run in alternation. The ixploration-focusee SGBS can help EAS avoid local optima, while EAS provides increasingly better models for SGBS to apply during search. Thus, the contribution of this paper is two-fold: (1) we introduce the novel beam-search method SGBS, and (2) we provide hybridized scheme using SGBS and EAS.
solution generation of
We show the effectiveness both of SGBS and the SGBS+EAS hybrid on a standard benchmark of the traveling salesperson problem (TSP), capacitated vehicle routing problem (CVRP), and the flexible flow shop problem (FFSP). SGBS outperforms sampling in all cases, and combining SGBS with EAS results in solutions to the TSP that have roughly two thirds the optimality gap of the previous state-of-the-ar thr neural CO solutions, and on the CVRP roughly half the gap. On the FFSP, SGBS provides solutions roughly equivalent to the state-of-the-an in an order of magnitude less time.
2 Related work
Neural combinatorial optimization The first application of modern deep learning methods to- wards a CO problem is offered by Vinyals et al. (7]. who use their newly proposed pointer network to generate solutions the TSP in an autoregressive manner. Their method has been improved by
reinforcement learning 3 and different network architectures CO problems like the CVRP has achieved state-of-the-ar performance on the autoregressive construction of TSP and CVRP so- lutions, using a new RL method that generates diverse CO solutions that compete with each other. For these TSP-like CO problems, transformer-base for colnecedd graphs, (but are more computationally expensive) are better suited and generally produce better quality solutions than the ordinary graph neural network (GNN), which are developed for universal graph topology.
12 13 Applications to other
8 4
have also been proposed. More recently, the POMO method [14]
neural models, which are highly specialized
Machine learning based improvement methods have also gained significant attention in the last years. Neural large neighborhood search (NLNS) [15) iteratively destroys a large part of a solu- tion and then repairs it. Iterative local search methods [16] 17 18 19), however, focus more on accumulating small changes (e.g., 2-opt) to a solution for improvement. The learning collaborative
policies (LCP) approach (20) first generates a diverse set of candidate solutions and then improves each solution using a second policy model.
While most works focus on small to medium scale problems, large scale approaches 21 22 have also been proposed that can solve the CVRP with up 2000 nodes by integrating a learning method with powerful operations research solvers. Neural approaches have been made for other various
Note that the ML community, especially for natural language processing (NLP), the term "beam search" almost exclusively refers to beam search in which the sampling probability of each node (i.e. the product of all probability values encountered when moving from the root to a particular node) plays the role of the ranking function. Throughout this paper, use "beam search" to mostly refer to this NLP-type beam search method.

---

types of CO problems, including routing problems [33 25 scheduling problems [16 26 27 13,
the satisfiability problems 28 29 automation 32 33
the graph problems 30 and electronic circuit design
Post-hoc tree searches used by neural CO methods Many neural CO methods use tree search or its variants (e.g.. beam search and MCTS) for selecting the final solution at test time. Autoregressive construction methods 7 [ use beam search as an optional post-hoc method to boost the solution quality. Many neural approaches for routing problems rely on predicted "heat map" that describes which edges will likely be part of an optimal solution. To generate the final solution, the heatmap is explored by, for example, beam search [34] 9 or by MCTS (35 36 While strictly not considered as CO problems, many successful neural approaches on turn-based games have exploited MCTS in their inference tactics (e.g.. (37]
Other similar works Tree search algorithms can benefit from utilizing deep neural networks in their branching and bounding mechanisms, as in learning-approachin MCTS [40], or branch and bound 41 MCTS variants that include beam width, bearing resem- blance to our work, have been proposed. However, unlike our method, they use random rollouts and do not require policy for guidance [3 < or lack the pre-selection mechanism propose [45]
beam search [38] (39],
Extensions of these variants have been successful at solving CO problems [46]
3
SGBS algorithm
3.1 Preliminaries
Consider CO problem with N decision variables ap, 01,''' ,aN-11 where assign a; with value from a finite domain X; for O<iIN-1 Our goal is to find a solution that maximizes the real- valued reward R. - R. The space S contains all possible solutions 8N (ao, .',,.. .vv-1). Constraints on the decision variables can be embedded in R by mapping infeasible solutions to negative infinity. In this sense, the reward function R directly represents the problem instances.
We construct a neural net Te parameterized by 0 and use it to generate a solution one step at a time. Defining the most effective order in which to construct a solution requires good architect, but here we assume a numerical order without loss of generality. For a partially completed (d < N) solution sa (ay, 01, probability distribution no(aalsa), Starting from an empty tuple 8p = (), this procedure repeats until complete solution sN (ao: 01, QN-1) is generated, which denote as s Tg.
ad-1), can choose value for aa sampled from X following the
In policy-based reinforcement learning, Te, 8a, ad: and R(sx) correspond a policy, state, action, and reward, respectively. Note that the reward is given only for the final state 8. in this case, and thus equivalent to what is commonly referred to as the 'return (total cumulative rewards)' of the episode. We train 0, the parameter of the policy neural network, with reinforcement learning method such that 0 is gradually updated by gradient ascent to increase the expected reward:
train RL.
argmax, PR [xx)s
(1)
Here, P refers to a (presumed) distribution of the target problem instances, from which we sample different reward functions R' used for training. This enables the neural net to exploit the limited size of the distribution P rather than having to train for the entire problem space. As long as the given target instance R is indeed a part of the distribution P. the policy network should perform well even though it has never encountered an identical problem instance before.
3.2
The algorithm and its three phases
The CO problem above can be viewed as a search problem in a decision tree where each node at depth d represents partially completed solution sa, and branches from this node represent different assignments to the (d+1)th decision variable, a,- The goal now is to find a terminal node s (or, equivalently, path from the root a leaf) maximizing the objective function.
The SGBS algorithm starts from the root node and builds search tree one depth level at a time (breadth-first). At each depth level, its search procedure is carried out in three phases: expansion,
3

---

Expansion
Simulation
Pruning
do
0000 o0000
0 oo
oooo
ooooo
Figure 1: Three phases of SGBS, illustrated with beam width 8 = 3 and expansion factor y 2. In the 'Expansion' figure we show an example of a tree consisting of number blue trajectories that represents a beam extended to depth 2. Of all its the possible child nodes, only 7 candidates (colored red) per each leaf node are selected. Wavy arrows in the 'Simulation' figure complete the rollouts, each earning different reward value. In the 'Pruning' figure, the beam grows by another depth, keeping its width size to 3 after pruning out the candidate nodes with poor performances.
simulation, and pruning (see Figure D. leaves most the "beam width (8)" number of nodes for that depth level and moves on to the next. The algorithm finishes when it reaches a level in which all the selected nodes are terminal. (A terminal node expands to itself, when not all nodes in the level are terminal.) Pseudocode for the SGBS algorithm is presented in Algorithm
Expansion (pre-pruning) The expansion phase of SGBS combination of the expansion step of the regular beam search (to all child nodes) and a pre-pruning step. Given an expansion factor Y a total of B x y child nodes are selected, while the rest are pprun) from the search tree. That is, for each node sa contained in the beam, the top of its child nodes with the largest To (-(-(aa) are selected, The total search time of SGBS increases (almost) linearly with and % so user can control the balance between the performance and the speed of SGBS by adjusting these parameters.
Simulation During this phase, the potential of each expanded child node is measured by rollout, similarly to the simulation phase of MCTS. We create 3 x y different CO solutions (simultaneously via parallel batch processing, if applicable) using greedy rollouts, and the rewards are tagged to the corresponding child nodes. Strictly speaking, child node's potential can be evaluated more accurately if multiple rollouts are used (e.g., repeated sampling, beam search or MCTS starting from the given node), but the use of single greedy rollout is good enough and more time efficient.
Algorithm Simulation-guidee Beam Search (SGBS)
1: procedure SGBS(trained model me, beam width B, expansion factor 7, reward function R)
B {so}
So the root node
3: while 3s, E B that is not a terminal node do
4:
E, S +- 2++0) (}, O
5: for s4 E B do
Expansion
6: add most y child nodes 8a+1 with highest probabilities To (-(-)))) 3) to F.
end for
8:
for 8241 E E do SN +- Grreeyyollout(s4n1 me)
> Simulation
9:
10:
add (sa+1, R(sx)) S
end for t- at most nodes 8241 with highest rewards R in S end while
12:
Pruning
13:
14:
return in B of highest R(sx)
15:
end procedure
*As alternative, one could group all child nodes together use sampling probability (accumulated from the root as is used by the NLP beam search) to select the top 3 x r child nodes. This exploitation focused approach, however, leads to worse search performance in our tests. The exploration (increased diversity from treating all nodes in the beam equals) seems play more important role than the exploitation at this stage.

---

(a) Pre-trained model
(b) Low-accuracy model
(c) Fine-tuned model
1.8
1.6
7.0
Gap (%)
1.4
Clep (%)
6.0
Gup (%)
0.7
1.2
5.0
1.0
0.6
4.0
0.8
Greedy
Sampling
Bean Search
Active Search
EAS MCTS
SGBS
Greedy
Samping
Beam Search
Active Search
EAS MCTS
SGBS
Gready
Sampligg ling
Beam Search
Active Search
EAS MCTS
SGBS
Figure 2: Performance of different search methods for the CVRP in three (a) scenarios. All methods evaluate the same number of candidate solutions per problem instance (1.2K candidates for (a) and (c), 2.4K for (b)). See Appendix C for implementation details. The gap is calculated with respect to solutions found with HGS 47 48
Pruning We select the nodes with the highest simulation scores and register them as the new beam front. Note that in SGBS, no complicated backpropagation processes follow the simulation phase, keeping the algorithm simple and efficient.
3.3 Strengths
The implementation of the SGBS algorithm a straightforward modification of the sampling method. It is also batch-process friendly, the simulation phase involves parallel greedy rollouts. Despite its simplicity, SGBS can provide good search results not easily accessible to other inference methods in most settings. In the following, we discuss three different, hypothetical environments encountered by a policy network solving CO problem and analyze how SGBS helps in each case.
A default setting (pre-trained to target distribution) Even if assume perfect training as prescribed in Eq. [ the gap between the target distribution /' and a single problem instance R will cause the neural network (limited by its finite capacity) to suggest incorrect decisions from time to time. SGBS is designed to correct these mistakes on the fly. When a child node of a partial solution sa given a relatively low score To To(aa)s (sa) by the policy network but in fact an ideal choice, the simulation step of SGBS can prevent premature pruning of this child node.
In Figure 2 (a), display the results of different search algorithms solving classic benchmark CO problem, the CVRP with 100 nodes. Greedy, sampling, and beam search methods generate solutions strictly based the probability distributions calculated by the neural network. Active search (3), EAS, MCTS, and SGBS are adaptive search methods that react to their past search results. All search methods use the output of an identical policy network and, for proper comparison, each method (except for greedy) returns its incumbent solution after investigating the same number (1.2K) of candidate solutions. We find that SGBS (8= 4 7= shows high search efficiency, outperforming most other inference methods, except for EAS
model with low accuracy (distribution shifts) The power of SGBS to find good solutions re- ally stands out when the policy network suffers from low accuracy. Dropping accuracy on a model's prediction common issue for many industry CO applications, where a sharp change the dis- tribution of the target problems are expected regularly. Without an inference method with good generalizability, these models have be re-trained frequently, which is difficult and expensive.
In Figure 2 (b), we illustrate this case by trying to solve the CVRP with 200 instances using the neural model from (a), which was trained with = 100 instances only. Now with the model
"Hottung et al. I provide three types of EAS methods in their paper: EAS Amb-, EAS-Lay, and EAS-Tab. For the sake of simplicity, throughout this paper we only use EAS- Lay and refer to it as just "EAS." EAS- is the easiest to implement, and it generally shows better performance among the three, especially for the CVRP.
5

---

having relatively low accuracy, we find that sampling and beam search methods output solutions that are even worse than the greedy one surprising result, in fact), exposing their vulnerability on distribution shifts. The adaptive search methods (Active Search, EAS, MCTS and SGBS), however, work well, with SGBS performing the best. Note that while MCTS shows similar search quality as SGBS, it is difficult to implement MCTS to utilize the parallel computing capacity of the GPU, making it very slow (~hours) compared to other methods (~-innttes) in our implementations.
Fine-tuned model (trapped at a local maximum) The quality of the CO solution can be en- hanced at test time 3 by fine-tuning the parameters of the neural network to the target instance:
line-tuning argmaxa Esy [R(sN)]
pre-trained 0
where R is specific to each target instance. Figure (c) shows the results of the same search pro- cedures used (a), with the only change being that the neural network fine-tuned toward each target problem before conducting the search. As expected, all search methods now produce much better solutions than they do without fine-tumine timeettuing...o The fine-tuned model, however, is overconfident in its first choices, and the good exploratory behavior of the model is lost it is now trapped in local optimum. SGBS is less affected by this confidence calibration issue 49 as its exploration range is firmly secured by the parameters / and 7. This also explains why the hybridization of SGBS with EAS (described in the next section) leads to such a significant performance boost.
4 SGBS + EAS
Despite being a very efficient inference method for neural CO tasks in the short run, the capability of SGBS in making the full use of given time budget is rather limited. First of all, SGBS is deterministic, so running it more than once offers no benefit. Its hyperparameters and y can be increased, but the gain quickly becomes marginal (see Appendix DD. In this section, we introduce the second neural CO inference method, a combination of SGBS and EAS, which can fully exploit the given computation time while still utilizing the powerful search mechanism of SGBS.
EAS adjusts small set of new parameters & in extra layers inserted into the original neural net (with the pre-trained parameters 0) using a loss function consisting of two components. The first, JRL. aims at reducing the expected costs of the generated solutions (as in active search 3 while the second loss, Jı,, encourages the model to output the incumbent solution with higher probability. We combine SGBS with EAS by running both methods in alternation (see Algorithm 2 with the incumbent solution and the model parameters being shared between both methods. SGBS is often able to improve the incumbent solution, helping EAS escape local optima while EAS constantly updates the model parameters, allowing SGBS to keep on growing new, non-overlapping search trees moving towards the more promising areas of the search space.
Within the inner loop of Algorithm 2 SGBS (line
Obj.
5) represents the majority of the computation, oc- cupying more than 75% of the overall runtime most of our SGBS+EAS experiments. However, we find that the enhanced search guidance from SGBS solutions is more than enough compen- sate for this. Figure 3 plots the averaged costs of the incumbent solutions found by EAS and SGBS+EAS over their runtime solving 10, 000 instances of CVRP with = 100. During the 30 hours plotted in the figure, EAS and SGBS+EAS update the policy networks 600 and 150 times, respectively, for each problem instance. In spite of the large difference in the backpropagation counts, the quality of the solution more than dou- bles when EAS gets help from SGBS.
EAS SGBS EAS
LKH3 (15.640)
15.675
HGS (15.563)
15.650
15.625
0.35%
0.23%
15.600
0.20%
0.11%
15:575
15.550
10
Hours
20
30
Figure 3: Performance of SGBS+EAS and EAS
10, 000 instances of CVRP with =000 compared to LKH3 and HGS results. Percent- age gaps displayed with respect to the HGS result at the runtimes of 6 and 30 hours.
Saving time on pre-training The parameters 0 and 36 of the policy network 7 used by SGBS+EAS are trained in a two-step process: (1) is "pre-trained" before the target problem is presented, using the known (or estimated) problem distribution (Eq. T). (2) z is "fine-tuned" at test

---

time, working with the given target instance (Algorithm 2 One might expect that pre-training 0 as much as possible before fine-tuning & would lead the best results. To our surprise, however, an over-trained 0 leads to worse performing SGBS+EAS, invoking the need for an early stop (see Appendix D All SGBS+EAS experiments presented in this paper use pre-trained models with such early stops applied. This calls for interesting follow-up research topics, such as incorporating entropy regularization to enhance SGBS+EAS.
We also find the implication of the reduced dependency on the pre-training stage noteworthy. One major drawback of using deep learning approach for real-world CO tasks is need for constant re-training of the base model whenever a large domain shift occurs. Regardless of how short the inference time is, a neural CO approach not viable if pre- training takes too long and cannot adapt to a changing environment. However, combining SGBS and EAS makes intensive pre- pre-training of the policy network less crucial. For example, takes only two hours to pre-train 0 from scratch to prepare neural model for SGBS+EAS, which then produces solutions for the CVRP with n 100 within a reasonable runtime and similar quality to those of LKH3 (see Appendix (H).
5 Experiments
We evaluate SGBS on various sizes of the TSP, CVRP, and FFSP instance sets with and without EAS. Our experiments carried out A100 GPUs (Nvidia) with 80 GB memory. We report the adjusted runtime under the premise that a single GPU has been used for each experiment.
TSP& & CVRP Table presents the SGBS(+EAS) results on two NP-hard routing problems, the TSP and CVRP. These two benchmarks are considered the most popular in the neural CO literature. In the TSP, given a instance consisting of nodes (cities), one needs to find the shortest tour visiting every node exactly once. In the CVRP, the nodes are assigned delivered from depot (starting node). The goal is to find the shortest-length tours that, together, visit all nodes exactly once and the sum of the demands on each tour do not exceed the capacity of the vehicle. For our experiments, we use n= 100 with 10,000 instances from Kool et 4 We also perform generalization (domain shift) experiments using = 150, 200 test sets of 1,000 instances from Hottung et al. [I]. We further explore the CVRP on a real-world like dataset in Appendix A
integer demand that must be
48 as the baseline for calculating the perfor- mance gaps in our TSP and CVRP experiments, respectively. Both are highly optimized, handcrafted solvers that produce (near- Joptimal solutions to each problem type. We also compare with the re- sults of LKH3, a well-known heuristic solver for hard routing problems. These non-neural solvers are CPU-bound and run single CPU only, so the wall-clock times we report in the table are not meant for direct comparison with GPU-computed numbers. Our results are compared against those of latest neural methods as well: DACT [19], NLNS (15). and DPDP (9]
We have followed Concorde 50 and HGS 47
We apply the SGBS methods on Transformer-like policy networks (attention model that have been pre-trained by the POMO [4] RL technique (MIT license). We perform ablation tests using the
Algorithm 2 SGBS+EAS
1: procedure SGBS+EAS(prc- CeBBStEAS(pre-trrinnnd teriiree-taieedddeeee model reward function R) siv - greedy solution generated from яe
s is the incumbent solution L is insertion layers for EAS
3: no. f- combine my and Ly with randomly initialized vb
4: repeat
5:
2% + SGBS (,,. 8,
Algorithm
6:
a/y # for i = 1,,,
7:
sx + sy in (sw, 8%,, six ... s of highest R(sN)
8:
VeJRR(() - M EM [[((s)) bo) EN- V log Na. (ag]s))
bo is baseline for REINFORCE
9:
Ju) EN- V. log (a xi))
10:
+ + a V + A V Jn() until has converged or timeout
Policy gradient ascent
12: return sty
13:
end procedure
7

---

Table I: Experiment results routing problems (TSP & CVRP)
Test (10K instances)
Generalization (IK instances)
Method
n 100
π
150
n
200
Ohj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Concorde LKH3
7.765
(82m)
9.346
(17m)
10.687 10.687
(31m)
7.765
0.000%
(8h)
9.346
0.000%
(99m)
0.000%
(3h)
DACT
19
7.771
0.089%
(8h)
DPDP
9
7.765
0.004%
(2h)
9.434
0.937%
(14m)
11.154
4.370%
(74m)
TSP
POMO
4
greedy
7.776
0.144%
(1m)
9.397
0,544%
(<Im)
10.843
1.459%
(1m)
sampling
7.771
0.078%
(3h)
9.378
0.335%
(1h)
10.838
1.417%
(3h)
EAS
1
7.769
0.053%
(3h) 9.363
0.172%
(1h) 10.731
0.413%
(3h)
7.768
0.044%
(15h)
9.358
0.127%
(10h)
10.719
0.302%
(30h)
SGBS (10.10)
7.769
0.058%
(9m)
9.367
0.220%
(8m)
10.753
0.619%
(14m)
SGBS+EAS
7.767
0.035%
(3h)
9.359
0.136%
(1h)
10.727
0.378%
(3h)
7.766
0.024%
(15h)
9.354
0.085%
(10h)
10.708
0.196%
(30h)
HGS
15.563
(54h)
19.055
(9h)
21.766
(17h)
LKH3
15.646
0.53%
(6d)
19.222
0.88%
(20h)
22.003
1.09%
(25h)
DACT
15.747
1.18%
(22h)
19.594
2.83%
(16h)
23.297
7.03%
(18h)
NLNS
15.994
2.77%
(1h)
19.962
4.76%
(12m)
23.021
5.76%
(24m)
CVRP
DPDP
15.627
0.41%
(23h)
19.312
1.35%
(5h) 22.263
2.28%
(9h)
POMO
4
greedy
15.763
1.29%
(2m)
19.636
3.05%
(1m) 22.896
5.19%
(1m)
sampling
15.663
0.64%
(6h) 19.478
2.22%
(2h) 23.176
6.48%
(5h)
EAS 1
15.618
0.35%
(6h)
19.205
0.79%
(2h) 22.023
1.18%
(5h)
15.599
0.23%
(30h)
19.137
0.54%
(20h)
21.980
0.98%
(50h)
SGBS (1,4)
15.659
0.62%
(10m)
19.426
1.95%
(4m)
22.567
3.68%
(9m)
SGBS+EAS
15.594
0.20%
(6h)
19.168
0.60%
(2h)
21.988
1.02%
(5h)
15.580
0.11%
(30h)
19.101
0.24%
(20h)
21.853
0.40%
(50h)
same models for greedy solution construction, sampling, and EAS. For all POMO-based methods we employ the x8 instance augmentation technique [4] to boost the solution quality. SGBS hyper- parameters set to (3, 7) (10, 10) and (4, 4) for the TSP and CVRP, respectively. These values have been chosen based on several trial runs of SGBS+EAS with some hand-picked sets of different choices. The overall search efficiency of SGBS+EAS (per unit runtime), however, is not that sen- sitive to the changes of these hyperparameters as long as they are within a reasonable range (see Appendix E). We report the results of SGBS+EAS (and EAS alone) two different points of their runtimes; one at an intermediate point and the other when the algorithm seems to have converged.
Overall, SGBS+EAS significantly outperforms all learned heuristics. On the three TSP instance sets, SGBS+EAS reduces the optimality gaps by 45%, 33%, and 35% from those of EAS, respectively. On the CVRP instances, SGBS+EAS not only outperforms EAS (52%, 56%, and 59% reduction in the gap), but also the well-known heuristic solver LKH3 by a large margin. With a gap of only 0. 11% to HGS on the CVRP instances with n= 100, we further observe that SGBS+EAS is competitive with state-of-the-art handcrafted techniques in terms of quality, albeit not in runtime.
FFSP To highlight the fact that SGBS is a general inference method for any construction-type neural approaches for CO task, not just for routing problems, we demonstrate its application on the flexible flow shop problem (FFSP), scheduling problem that can arise (e.g.) in factory assembly lines. In the FFSP, jobs are processed by multiple stages in series, where each stage consists of a group of machines that perform the same task but possibly at different speeds. Each machine can handle only one job at a time so that a scheduling method needed to decide which jobs to be processed on which machine at what time to achieve the shortest possible makespan.
We apply SGBS on the MatNet datasets of 1, 000 FFSP instances each for n= 20, 50 and 100 jobs. These instances [13] are based on three-stage configurations where each stage contains four different machines. The details of our SGBS experiments on the FFSP are described in Appendix G Results of our SGBS experiments
B based neural FFSP solver (MIT license) and experiment on the
and the ablation studies are summarized in Table with the results 13 by CPLEX (1 with
mixed-integer programming models and meta-heuristic solvers.
8

---

Table 2: Experiment results on 1, 000 instances of FFSP
FFSP20 Gap
FFSP50
SFO0
Method
Obj.
Time
Obj.
Gap
Time
Obj.
Gap
Time
CPLEX (60s)
46.37
22.07
(17h)
x
CPLEX (600s)
36.56
12.26
(167h)
Genetic Algorithm
30.57
6.27
(56h)
56.37
8.02
(128h)
98.69
10.46
(232h)
Particle Swarm Opt.
29.07
4.77
(104h)
55.11
6.76
(20Sh)
97.32
9.09
(384hh
MaiNet
13
greedy
25.38
1.08
(3m)
49.63
1.28
(8m)
89.70
1.47
(23m)
sampling
24.60
0.30
(10h)
48.78
0.43
(20h)
88 .5
0.72
(40h)
EAS
24.60
0.30
(10h)
48.91
0.56
(20h)
88.94
0.71
(40h)
24.44
0.14
(50h)
48.56
0.21
(100h)
88.57
0.34
(200h)
SGBS (5.6)
24.96
0.66
(12m)
49.13
0.78
(47m)
89.21
0.98
(3h)
SGBS+EAS
24.52
0.22
(10h)
48.60
0.25
(20h)
88 88.56
0.33
(40h)
24.30
(50h)
48.35
(100h)
88 88.23
(200h)
As shown in the table, SGBS+EAS significantly outperforms the baseline traditional CO methods. While we do not claim that our approach the state-of-the-art over existing (neural or not) methods for the FFSP, this result shows that, at the very least, without careful design by a domain expert, non-ncural approaches do not yield satisfactory solutions to many complicated CO problems. MatNet-based solvers, the other hand, able to produce solutions of extremely high quality, highlighting the advantage of neural CO approaches, that are automatic and purely data-driven. We have also shown that simple change the inference technique SGBS+EBS empowers the existing neural solver to produce solutions that have been unattainable within a reasonable runtime.
Conclusion
We have presented Simulation-guided Beam Search (SGBS) and combined with EAS solve CO problems. SGBS enables neural CO methods to effectively search for high-quality solutions to CO problems and can be implemented easily in existing approaches. Furthermore, we show that com- bining SGBS with EAS allows for even better performance as the two techniques share information about finding solutions. Our experiments on three different CO problem settings, the TSP, CVRP and FFSP, further reduce the gap of neural CO methods to state-of-the-e and in some cases beat methods that were state-of-the-aar only a few years ago. For future work, we plan to explore setting up dynamically the parameters of SGBS and investigate the integration of SGBS and EAS more deeply.
handcrafted heuristics
Our code for the experiments described in the paper is publicly available at atthtps:///ee htt::://gtttu..ooom yd=kwwn/SGBS
Acknowledgments and Disclosure of Funding
Some of the computational experiments in this work have been performed using the Bielefeld GPU Cluster. thank the Bielefeld HPC.NRW team for their support. Furthermore, the authors grate- fully acknowledge the funding of this project by computing time provided by the Paderborn Center for Parallel Computing (PC2).

---

References
[1] André Hottung, Yeong. Dae Kwon, and Kevin Tiemey. Efficient active search for combinatorial optimiza- tion problems. International Conference un Learning Representations, 2022.
[2] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost, Machine learning for combinatorial optimization: a methodological tour d' horizon. European Journal of Operational Research, 2020.
[3] Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. ICLR (Workshop), 2017.
[4] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! International Conference Learning Representations, 2019.
[5] Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In Machine Learning: ECML 2006, pages 282-293, Berlin, Heidelberg. 2006. Springer Berlin Heidelberg.
[6] Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. Computers and Games, pages 72- 83, Berlin, Heidelberg. 2007. Springer Berlin Heidelberg.
[7] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Information Processing Systems 28, 2015.
[8] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement lcarning for solving the vehicle routing problem. Advances in Neural Information Processing Systems 31, 2018.
[9] Wouter Kool, Herke Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing prohlems. arXiv preprint arXiv:2 1756, 2021.
[10] Chaitanya Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travel- ling salesperson problem requires rethinking generalization. Constraints, pages 1-29, 2022.
[11] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems 30, 2017.
[12] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martie Rousscau. Learning heuristics for the TSP by policy gradient. In International Conference on the Integration of Con- struint Programming, Artificial Intelligence, and Operations Research, pages 170-181. Springer, 2018
[13] Yeong-Dac Kwon, Jinho Choo, Tijoo Yaon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems 34, 2021.
[14] Yeong-Dac DDe Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neurul Information Processing Systems 33, 2020.
[15] André Hottung and Kevin Tiemey. Neural large neighborhood search for the capacitated vehicle routing problem. European Conference on Artificial Intelligence, pages 443-450 2020.
[16] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Syxtems 32, 2019.
[17] Paulo R. de O. da Costa, Jason Rhuggenaath, Yingqian Zhang. and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. ACML, pages 465-480 480, 2020.
[18] Yaoxin Wu. Wen Song. Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks, 2021.
[19] 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 Neural Information Processing Systems 34, pages 11096-11107, 2021.
[20] Minsu Kim, Jinkyoo Park, and Joungho Kim. Learning collaborative policies to solve np- routing problems. Advances in Neural Information Processing Systems 34, pages 10418-1044 2021.
[21] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems 34, 2021.
10

---

[22] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with lin- kernighan-hehagaun heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems 34, 2021.
[23] Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with combinato- rial actions: An application to vehicle routing. Advances Neural Information Processing Systems 33, pages 609-620,200 2020.
[24] 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 Intel- ligence, volume 35, pages 12042-12049, 2021.
[25] Yining Ma. Jingwen Li, Zhiguang Cao. Wen Song. Hongliang Guo, Yuejiao Gong, and Yeow Meng Chee. Efficient neural neighborhood search for pickup and delivery problems, arXiv preprint arXiv:2204. 1339, 2022.
[26] Chun-Cheng Lin, Der-Jiunn Deng, Yen-Ling Chih, and Tiin Chiu. Smart manufacturing scheduling with edge computing using multiclass deep q network. IEEE Transactions on Industrial Informatics. 15(7):4276-4283 2019.
[27] Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Advances in Neural Information Processing Syxtems 33, pages 1621-1633 2020.
[28] Emre Yolcu and Barnahás Póczos. Learning local search heuristics for boolean satisfiabilityy. Advances in Neural Information Processing Systems 32, 2019.
[29] Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. Can q-learning with graph networks learn generalizable branching heuristic for sat solver? Advances in Neural Information Processing Systems 33, pages 9608 9621, 2020.
[30] Zhuwen Li, Qifeng Chen, and Vladlen Koltun, Combinatorial optimization with graph convolutional networks and guided tree search. Advances in Neural Information Processing Systems 31, 2018.
[31] Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial opti- mization with reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3243-3250, 2020.
[32] Ruoyu Cheng and Junchi Yan. On joint learning for solving placement and routing in chip design. Ad- vances in Neural Information Processing Systems 34, 2021.
[33] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ehrahim Songhori, Shen Wang. Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al. A graph placement methodology for fast chip design. Nature, 594(7862):207-212 2021.
[34] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. INFORMS Annual Meeting 2019, Session Boosting Combinatorial Optimization using Machine Learning.
[35] Zhihao Xing and Shikui Tu. graph neural network assisted monte carlo tree search approach traveling salesman problem. IEEE Access, 8: 108418-108428, 2020.
[36] Zhang-Hur Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7474-7482. 2021.
[37] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schritwieseer, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Do- minik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukeuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 489, Jan 2016.
[38] Renato Negrinho, Matthew Gormlcy, and Geoffrey Gordon. Learning beam search policies via imitation lcarning, Advances in Neural Information Processing Systems 3/, 2018
[39] Mare Huber and Günther R Raidl. Learning beam search: Utilizing machine learning to guide beam search for solving combinatorial optimization problems. In International Conference on Machine Learning. Optimization, and Data Science, pages 283-298. Springer, 2021.
11

---

[40] Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving up-hard problems on graphs with extended alphago arXiv preprint arXiv:1905.11622 2019.
[41] Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning branch in mixed integer programming. Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016.
[42] André Hottung, Shunji Tanaka, and Kevin Tiemny. Deep learning assisted heuristic tree search for container pre-marshallig problem. Computers Operations Research, 113:104781, 2020.
[43] Tristan Cazenave. Monte carlo beam search. IEEE Transactions on Computational Intelligence and Al in games, 4(1):68-77 72,8887722888 2012.
[44] Hendrik Baier and Mark HM Winands. Beam monte-carlo tree search. In 2012 IEEE Conference on Computational Intelligence and Games (CIG), pages 227-233. IEEE, 2012.
[45] Jorik Jooken, Pieter Leyman, Patrick De Causmaecker, and Tony Wauters. Exploring search space trees using adapted version of monte carlo tree search for combinatorial optimization problems. arXiv preprint arXiv:2010. 11523, 2020.
[46] Stefan Edelkamp, Max Gath, Tristan Cazenave, Fabien Teytaud. Algorithm and knowledge engi- neering for the tsptw problem. In 2013 IEEE Symposium on Computational Intelligence Scheduling (CISched), pages 44-51 IEEE, 2013.
[47] Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):611- 624, 2012.
[48] Thibaut Vidal. Hybrid genetic search for the evrp: Open source implementation and swap" neighborhood. Computers Operations Research, 140:105643, 2022.
[49] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Weinberger. On calibration of modern neural networks.
In Proceedings of the 34th International Conference on Machine Learning, volume 70, 2017.
[50] David L Applegate,, Robert Bixby, Vasek Chvatal, and William Cook. The traveling salesman problem:
a computtaional study. Princeton university press, 2006.
[51] IBM ILOG CPLEX Optimization Studio. V20.1: User's Manual for CPLEX. IBM Corp, 2020.
[52] Keld Helsgaun, An Extension of the Lin Kon-Kernighan-Heee TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report. Roskilde Universitet, December 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] They do.
(b) Did you describe the limitations of your work? Yes]] There is a limitation on increas- ing and 7, which we have discussed in Section and Section 4
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work deals with abstract problems, so we think it is too early to discuss its potential societal impacts this point.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Our paper conforms the guidelines.
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as URL)? [Yes] URL. provided in
12

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section Some details are also provided in the Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] Our main results are based experiments large
> 1000 number of problem instances.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section [
4. If you using existing assets (c.g., code, data, models) curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use existing
codes and datasets. We cite the creators.
(b) Did you mention the license of the assets? [Yes] We mention the licenses.
(c) Did you include any new assets either in the supplemental material or as URL? [No] We do not.
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [No] Dataset we use is publicly available numerical synthetic data.
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "LKx2UlXg2FI", "reviewer": "Reviewer_7y6f", "summary": "This paper proposes two novel methods for neural-network-based combinatorial optimization.\nThe two methods, SGBS and SGBS+EAS show promising performance for solving three types of combinatorial optimization problems (TSP, CVRP, and FFSP).\n", "questions": "In my understanding, in the EAS paper [1], the solutions are simply sampled from the model.\nWas there any theoretical/practical difficulty in extending the idea to MCTS?\n\nI agree that SGBS easily utilizes batch parallelism, but it is not the only way.\nHave you considered comparing the proposed method with existing parallel MCTS?\nIn my intuition, parallel MCTS equipped with progressive widening may also perform.\n\n---\nPost rebuttal comments.\n\nThank you for the detailed comment.\nHowever, I did not think I needed to change my score.", "limitations": "There is a discussion about the two hyperparameters $\\beta$ and $\\gamma$.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe authors proposed Simulation-Guided Beam Search (SGBS), combining Monte-Carlo Tree Search (MCTS) and beam search.\nSBGS is also combined with an interesting existing technique, Efficient Active Search (EAS), which updates a small part of the network during the search.\nThe experiments show that SGBS+EAS performs better than many existing approaches.\n\nWeaknesses:\nThe novelty is somewhat limited.\nThe key idea of EAS is already proposed in [1].\nSGBS is very similar to an existing work, Monte-Carlo Beam Search [41].\nThe contribution of this paper is to prove that EAS works well when combined with MCTS.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HTrnFtLESRt", "reviewer": "Reviewer_q7i4", "summary": "The paper presents a Beam Search strategy augmented with Monte Carlo Rollouts evaluating the “return” potential of a sampled action, instead of the commonly used policy likelihood. Besides the immediate advantage of using a search mechanism on top of a network inference (as opposed to a single-shot inference), the paper highlights that the rollouts can act as a recourse mechanism to rectify incorrect decisions made by the network (when selecting the top-k most likely actions). To leverage the additional time allocated to the generation of a solution, the method is combined with the recently published Efficient Active Search (EAS) method. The paper shows interesting synergies between these two components. The approach and its variants are validated on a set of combinatorial optimization problems (TSP, CVRP, FFSP) as well as compared to Beam Search, EAS, MCTS and non-adaptive methods.", "questions": "- The rollout mechanism depends on the neural network as well — Could an argument be made against the fact that we assume that the network might make a mistake at step *t* but then takes a sensible sequence of greedy actions till the end of the episode (recourse mechanism of the SGBS)?\n- Caption of Fig 2: “All methods evaluate the same number of candidate solutions per problem instance.” Can you describe what it means in terms of MCTS simulations, Gradient descents applied to the network for Active Search, etc?\n- Fig 2 - What do these numbers vary as we grow or reduce the compute budget. Here the setup has been set to favour SGBS using (β = 4, γ = 4). Does the MCTS reach a higher asymptotic performance when given additional time? Given that the authors mentioned in the appendix that SGBS quickly plateaus, where (resources) do the methods cross in terms of performance? I'm surprised that a simple Beam Search with a random rollout to evaluate the nodes outperform the more structured MCTS search. Could the authors provide additional details on this?\n- Fig 2c - why does the MCTS’s performance not follow the same performance trend as the SGBS when fine-tuning the model? SGBS seems to benefit more than the MCTS when the model is fine-tuned.\n- I haven’t found the implementation of the MCTS or the Beam/SGBS search in the code linked to the paper. It seems that only the networks and environments are made available. Will that change in the future?", "limitations": "-", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**\n\nThe method presented is relatively simple, i.e. augmenting the beam search procedure with greedy rollouts. Although I'm not aware of the exact same scheme being published before, the originality of the method is limited. In addition, most of the performance is driven by EAS. Interesting synergies are highlighted and constitute a novel contribution. Overall, although the method is well described and investigated, the originality and contribution are slightly under expectations.\n\n**Significance**\n\nMachine Learning for Combinatorial optimization problems is an important area of research as this family of problem it underlies many real-life applications. I don't consider the search mechanism to be of significant importance but rather see an interest in the discussion around EAS + SGBS. The search is however a good suggestion for practitioners to easily implement a lookahead mechanism (easier and more scalable than MCTS). \n\n**Quality:**\n\nThe paper is technically strong. The results are well reported (tables and figs), documented and discussed. The balance in the level of details provided in the main text and the appendix is adequate for the reader.\n\n**Clarity:**\n\nThe quality of the writing meets the expected standards. The content is well structured and logically organized. The results are appropriately reported and discussed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7XqyiWvaZ_J", "reviewer": "Reviewer_T9pd", "summary": "This paper considers the problem of solving NP-hard combinatorial optimisation (CO) problems efficiently and near-optimally using machine learning, specifically in the context of beam search. Recent works have sought to use neural networks to evaluate and select candidates with the beam search optimisation heuristic, iteratively building partial solutions with the use of a decision tree in a breadth-first search manner until a near-optimal solution is found. However, such approaches are vulnerable to poor action evaluations made by any of the neural network’s imperfect predictions, which can be detrimental to overall performance.\n\nTo address this, the authors propose a simple algorithm, simulation-guided beam search (SGBS), which combines neural beam search with simulated rollouts similar to those used in Monte Carlo Tree Search (MCTS) algorithms but without the need for potentially complex state-action value backpropagation. Specifically, at each step in constructing the partial CO solution and the next depth-layer of the search tree, SGBS selects a group of candidate actions using a neural network to predict their complete CO solution score. It then simulates a greedy rollout from each of these actions to their terminal states, and then selects a sub-group (with size equal to the beam width) of these initially marked candidate actions to save in the search tree as the beam front, thus pruning initially marked actions with ultimately poor outcomes from the final search tree/solution. This process is repeated until a complete CO solution is found from root to leaf in the search tree.\n\nAlthough SGBS alone performs well in time-restricted settings, the authors note that practitioners sometimes prefer allocating larger time budgets to find more optimal solutions. Since SGBS is a deterministic heuristic, it receives no benefit from larger time budgets other than adjustment of its hyperparameters, $\\beta$ and $\\gamma$, which the authors show have limited effect on performance beyond a certain point (which is quickly reached). To address this, the authors combine SGBS with the recently published ‘efficient active search’ (EAS) method of Hottung et al. 2022 to create a new algorithm, SGBS-EAS. The authors show that SGBS and EAS have a symbiotic relationship with one another whereby SGBS helps EAS to avoid local optimal while EAS provides an increasingly performant neural network model during test-time. Both SGBS and SGBS-EAS are shown to outperform some canonical CO heuristics and state-of-the-art ML solvers in both solution quality and solving time.", "questions": "* **Context and related work:** The proposed SGBS and SGBS-EAS algorithms, as well as the baseline agents compared to, rely on relatively expensive (in terms of both training time and inference) transformer models with additional training overhead at test time and/or simulated rollouts. Can the authors comment on how such techniques compare to other state-of-the-art ML-CO methods based on cheaper graph neural network models which do not require simulated rollouts (Dai et al. 2017, Abe et al. 2019, Li et al. 2018, Barrett et al. 2020 and 2022, Drori et al. 2020)? Would there be differences in optimality and training and inference time performance? Might the training overhead of EAS at test time incur disadvantages at test time in terms of both inference time and solution efficacy when initially deployed? How does SGBS/SGBS-EAS fit in the context of these other literature contributions?\n\n* **Reward function:** In the SGBS Methodology section, the authors state that $P$ represents a set of target problem instances from which they sample different ‘reward functions’ $R’(S_N)$ during training, which enables the neural network to exploit the limited size of the distribution $P$ rather than having to train for the entire problem space. I’m not entire sure what this means - is it that $S_N$ (i.e. the final solution found by the RL agent) is changing and therefore that the total return evaluated by the reward function is changing (since the RL agent explores during training), or are the authors actually using different reward functions to evaluate the same solution $S_N$ in different ways? If the latter, what reward functions are used? How can the RL agent learn to predict the values of states and actions when the reward function in the MDP is changing? I do not entirely follow this MDP formulation or which reward function(s) were used for each CO problem class.\n\n* **Action sampling methodology:** What policy is used for selecting actions in the SGBS greedy rollouts? Is it just the argmax of the $\\pi_\\theta(\\cdot | s_{d})$ policy of the neural network, or some other heuristic?\n\n\n### Miscellaneous minor issues\n* Fig 1: Would be useful to have a key showing what the different colours, fills, and shapes of search tree edges and nodes mean. Also it may be helpful to add in the caption that Fig 1 is an SGBS step at $d=2$ for clarity\n\n* Pg 7 line 218: ‘the’ typo: ‘...are displayed with the respect to...’\n\n* Pg 4 line 129: Should ‘...the rewards are tagged to the...’ be ‘...the returns are tagged to the...’ given standard RL jargon which refers to per-step evaluation signals as rewards and total cumulative rewards across the episode as returns?\n\n\n### References\n\n* Andre Hottung, Yeong-Dae Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. International Conference on Learning Representations, 2022.\n* Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, 2017\n* Kenshin Abe, Zijian Xu, Issei Sato, and Masashi Sugiyama. Solving NP-Hard Problems on Graphs by Reinforcement Learning without Domain Knowledge. arXiv:1905.11623, 2019\n* Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. In Advances in Neural Information Processing Systems, 2018\n* Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020\n* Thomas D. Barrett, Christopher W. F. Parsonson, and Alexandre Laterre. Learning to solve combinatorial graph partitioning problems via efficient exploration. arXiv:2205.14105, 2022\n* Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. arXiv:2006.03750, 2020", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong points:\n* All sections of the paper are excellently written and easy to understand.\n* As far as I am aware, the idea to combine neural beam search and simulated rollouts in this way is novel, even if it is simple.\n* The proposed method is easy to implement and integrate with existing neural beam search techniques.\n* The experimental results outperform baselines on standard NP-hard CO problems; an important and significant application area of ML.\n\nWeak points:\n* Lack of comparison to/discussion of some other state-of-the-art graph neural network techniques which do not require simulated rollouts or search trees (see below).\n* A few things which could be clarified (see below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2RTDTDSyaAf", "reviewer": "Reviewer_QRWC", "summary": "This paper introduces a general approach for solving combinatorial optimization problems using a hybrid Beam-Search approach that can update it's policy on the fly. In contrast to work that focuses on improving policy towards getting solutions in a single shot, this work attempts to make better use of available computation.  One trick here is replacing the compute-intensive MTCS with a simpler Beam-search to pick rollout candidates. Additionally, the authors use EAS to update the policy network to make more effective choices at test time. This paper contribution is in domains where queries to a ground truth simulator are cheap but the search space is combinatorial. ", "questions": ".", "limitations": "I'm limited in my ability to evaluate this paper, especially in the broader context. I read the paper, and understand the main points, but I cannot place it in the wider literature. \n\nI'm confident it is well executed, and sensible in it's approach. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- Well-motivated paper. \n- Clean execution. \n- Code is provided and readable. \n- Algorithm is tested on reasonable benchmarks.\n\n- I appreciated the section on the algorithm's strengths. \n\n\n### Weaknesses\nOverall I found it a good paper, no major flaws. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept