PaperlayerView exact revision on arXiv

Source-linked AI summary

Simulation-guided Beam Search for Neural Combinatorial Optimization

Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tierney, Youngjune Gwon

arXiv:2207.06190v3cs.LGcs.AI

TL;DR

Neural combinatorial optimization methods can struggle to use available solving time effectively, while existing search approaches have trade-offs in guidance or runtime. Simulation-guided beam search (SGBS) combines policy-guided beam expansion with rollouts, and can be paired with efficient active search (EAS). Across TSP, CVRP, and FFSP benchmarks, SGBS improves on sampling, with the hybrid achieving smaller optimality gaps on TSP and CVRP and SGBS matching FFSP quality in less time.

  • Problem

    Neural CO search needs to exploit inference time without relying only on network predictions or the potentially resource-intensive rollouts of MCTS.

    Source: §1 · pp. 1–2

  • Method

    SGBS uses rollouts to guide expansion of promising nodes identified by a neural policy, and alternates with EAS to improve search guidance and the policy.

    Source: §1 · p. 2

  • Results

    Across TSP, CVRP, and FFSP, SGBS outperforms sampling; SGBS+EAS reaches roughly two thirds the previous state-of-the-art neural CO optimality gap on TSP and roughly half on CVRP, while SGBS matches FFSP quality in an order of magnitude less time.

    Source: §1 · p. 2

  • Takeaways & Limitations

    SGBS provides neural CO with an efficient search procedure that improves solution quality over sampling across the reported benchmarks.

    Source: §1 · p. 2

    SGBS is deterministic, so repeated runs offer no benefit, and increasing β and γ yields quickly marginal gains.

    Source: §4 · p. 6

Abstract

from arXiv · show

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.

1 Introduction

Neural combinatorial optimization learns heuristics for CO, but effective inference that uses available solving time remains underexplored. The paper introduces SGBS and an SGBS+EAS hybrid, reporting improvements across TSP, CVRP, and FFSP benchmarks.

1 Introduction

  • Neural CO methods learn dataset-customized heuristics, but research has emphasized single-shot policy quality more than inference that uses a given time budget.Practitioners of many industrial CO tasks may wait even multiple days for high-quality solutions.Source: §1 · p. 1
  • Sampling improves on greedy construction but its gains quickly diminish, MCTS can be resource intensive, and beam search can blindly follow poor network predictions.These limitations motivate guided search that combines network policy information with simulation.Source: §1 · pp. 1–2
  • SGBS combines MCTS with beam search, using rollouts to assess network-selected promising nodes and retain promising candidates for further expansion.Its implementation requires little modification to sampling inference and avoids complicated backpropagation that would prevent batch parallelization.Source: §1 · p. 2
  • SGBS and EAS alternate synergistically: SGBS solution exploration helps EAS avoid local optima, while EAS improves the model used by SGBS.The paper presents both SGBS and a hybrid scheme combining it with EAS [1].Source: §1 · p. 2
  • SGBS outperforms sampling on TSP, CVRP, and FFSP; SGBS+EAS reaches roughly two thirds the previous state-of-the-art neural CO optimality gap on TSP and roughly half on CVRP.On FFSP, SGBS gives solutions roughly equivalent to the state-of-the-art in an order of magnitude less time.Source: §1 · p. 2

2 Related work

Related work spans neural construction and improvement methods, neural-guided tree search, and large-scale CO approaches that combine learning with operations-research solvers. SGBS is distinguished from related beam-width MCTS variants by its policy-guided preselection and rollout procedure.

2 Related work

  • Neural construction research includes pointer-network TSP methods, reinforcement-learning and architecture variants [3] [13], CVRP applications [8], and POMO for TSP and CVRP [14].Transformer models are described as better suited to TSP-like fully connected graphs and generally higher quality than ordinary GNNs, but more computationally expensive.Source: §2 · p. 2
  • Neural improvement methods include destroy-and-repair NLNS [15], iterative local search accumulating small changes [16] [17] [19], and LCP, which improves diverse candidates with a second policy [20].Source: §2 · p. 2
  • Large-scale approaches integrate learning with operations-research solvers to solve CVRP instances with up to 2000 nodes [21].Source: §2 · p. 2
  • In this paper's terminology, “beam search” usually means NLP-style search ranked by the product of node probabilities along a path.Source: §2 · p. 2
  • Neural CO methods use beam search or MCTS for final selection, including search over autoregressive constructions [8] and predicted routing heat maps [34] [9] [36].MCTS is also used in neural turn-based-game inference.Source: §2 · p. 3
  • Related beam-width MCTS variants use random rollouts without a guidance policy or lack SGBS's preselection mechanism [45].Other learning-based work applies neural networks to beam search [38], MCTS [40], and branch-and-bound; extensions of the variants have solved CO problems.Source: §2 · p. 3

3 SGBS algorithm

SGBS uses a neural policy to construct candidate solutions and simulation rollouts to guide a fixed-width tree search. Its reported strengths include strong performance under distribution shift and reduced vulnerability to overconfident fine-tuned policies.

3.1 Preliminaries

  • A policy πθ generates a CO solution one decision at a time by sampling each next assignment conditioned on the partial solution.The target instance is assumed to belong to the problem-instance distribution P used for training; the passage says this supports performance on unseen identical instances.Source: §3.1 · p. 3

3.2 The algorithm and its three phases

  • SGBS expands each beam node to its γ highest-probability children, simulates each with a greedy rollout, then retains the β children with the highest rollout rewards.Expansion selects β × γ children overall, and search time increases almost linearly with β and γ; Figure 1 illustrates expansion, rollout simulation, and pruning.Source: §3.2 · p. 4, Figure 1 · p. 4
  • Treating beam nodes equally during preselection increases diversity and performed better in the authors’ tests than ranking all children by accumulated root-to-node probability.Source: §3.2 · p. 4

3.3 Strengths

  • SGBS's simulation can prevent premature pruning when the policy gives a low probability to an ideal next choice.It is batch-process friendly because rollouts can run in parallel, and avoids complicated backpropagation after simulation.Source: §3.3 · p. 5, §3.2 · p. 5
  • With a CVRP n = 100 instance and equal candidate counts, SGBS (β = 4, γ = 4) outperforms most compared inference methods except EAS.Figure 2 compares CVRP search methods across three scenarios, with the gap calculated against HGS [47, 48].Source: §3.3 · p. 5, Figure 2 · p. 5
  • Under distribution shift, SGBS performs best among the compared adaptive search methods, while sampling and beam search can produce solutions worse than greedy.The comparison uses a model trained on CVRP n = 100 instances to solve n = 200 instances; MCTS has similar search quality but takes roughly hours rather than minutes in the authors’ implementations.Source: §3.3 · pp. 5–6
  • Fine-tuning makes all compared search methods produce better solutions, but can make the policy overconfident and trapped in a local optimum; SGBS is less affected because β and γ secure its exploration range.The passage connects this behavior to the performance boost from combining SGBS with EAS.Source: §3.3 · p. 6

4 SGBS + EAS

SGBS and EAS alternate while sharing the incumbent solution and model parameters: SGBS improves the incumbent, and EAS updates the policy used in subsequent searches. The combination improves solution quality, but SGBS alone has limited ability to use longer time budgets.

4 SGBS + EAS

  • SGBS is deterministic, so rerunning it offers no benefit, and increasing β and γ yields quickly marginal gains.The authors introduce SGBS+EAS to better exploit longer computation budgets while retaining SGBS search.Source: §4 · p. 6
  • SGBS and EAS alternate while sharing the incumbent and model parameters; SGBS improves the incumbent, while EAS updates the policy for further searches.SGBS solutions help EAS escape local optima, and EAS lets SGBS grow new, non-overlapping search trees.Source: §4 · p. 6
  • After 30 hours on 10,000 CVRP instances with n=100, solution quality more than doubles with SGBS+EAS despite 150 rather than 600 policy updates per instance.SGBS occupies more than 75% of runtime in most SGBS+EAS experiments.Source: §4 · p. 6, Figure 3 · p. 6
  • Over-training the pre-trained parameters θ worsens SGBS+EAS performance, so the experiments use early-stopped models.The authors note that two hours of pre-training from scratch can prepare a model that produces CVRP n=100 solutions similar in quality to LKH3 within reasonable runtime.Source: §4 · p. 7

5 Experiments

The experiments evaluate SGBS with and without EAS on TSP, CVRP, and FFSP, including routing tests under domain shift. They compare neural and handcrafted methods and report adjusted runtimes assuming one GPU per experiment.

5 Experiments

  • The experiments use A100 GPUs with 80 GB memory and report adjusted runtimes under a one-GPU-per-experiment assumption.SGBS is applied to attention-model policy networks pre-trained using POMO reinforcement learning.Source: §5 · p. 7
  • Experiments cover TSP and CVRP at n=100 and domain-shift tests at n=150 and 200, with a separate real-world-like CVRP dataset explored in the appendix.The n=100 sets contain 10,000 instances, while the domain-shift sets contain 1,000 each.Source: §5 · p. 7
  • Routing results are compared with Concorde for TSP, HGS for CVRP, LKH3, and neural methods DACT, NLNS, and DPDP.The handcrafted CPU baselines run on a single CPU, so their wall-clock times are not directly comparable to GPU runtimes.Source: §5 · p. 7

N 13: end procedure

SGBS+EAS improves on EAS and other learned heuristics across routing benchmarks, and its FFSP results outperform baseline traditional CO methods. The experiments also apply SGBS to a neural scheduling solver.

Routing results

  • SGBS+EAS cuts EAS optimality gaps 45%, 33%, and 35% on TSP and 52%, 56%, and 59% on CVRP; CVRP n=100 gap to HGS is 0.11%.The authors report that SGBS+EAS outperforms LKH3 on the CVRP instances, though not in runtime.Source: Table 1 · p. 8, N 13: end procedure · p. 8
  • For routing, the authors report SGBS+EAS and EAS at an intermediate runtime and again when each algorithm seems to have converged.The table covers TSP and CVRP results.Source: N 13: end procedure · p. 8, Table 1 · p. 8

FFSP

  • The FFSP evaluation uses 1,000 instances each for n=20, 50, and 100 jobs, based on three-stage configurations with four machines per stage.The comparison includes CPLEX, meta-heuristic solvers, and MatNet-based neural solver results.Source: N 13: end procedure · p. 8, Table 2 · p. 9
  • On FFSP, SGBS+EAS significantly outperforms baseline traditional CO methods, though the authors do not claim it is state of the art overall.The authors describe applying a change in inference technique to an existing neural solver.Source: N 13: end procedure · p. 9, Table 2 · p. 9

6 Conclusion

The paper presents SGBS and its combination with EAS for neural combinatorial optimization. Experiments on TSP, CVRP, and FFSP reduce the gap to handcrafted heuristics, and the authors identify dynamic parameter setting and deeper integration as future work.

6 Conclusion

  • Across TSP, CVRP, and FFSP, the experiments reduce neural CO methods’ gap to state-of-the-art handcrafted heuristics, sometimes beating methods that were state of the art only a few years earlier.The conclusion says SGBS+EAS improves performance by sharing information about finding solutions.Source: §6 · p. 9
  • SGBS is presented as a search procedure for neural CO that can be implemented in existing approaches.The paper also reports publicly available experimental code.Source: §6 · p. 9
  • Future work will explore dynamically setting SGBS parameters and more deeply integrating SGBS with EAS.Source: §6 · p. 9

A Performance on real-world based instances

Across nine real-world-based CVRP instance sets, SGBS+EAS substantially outperforms EAS and LKH3, and nearly matches HGS. Its rollout implementation avoids repeating a candidate already examined in the prior simulation phase.

A Performance on real-world based instances

  • The evaluation trains a separate POMO model for each of nine instance sets, which contain 20 instances sampled from a shared underlying distribution.Instances are solved sequentially, a setting described as slightly unfavorable to SGBS+EAS because it is designed to exploit GPU parallelism.Source: A Performance on real-world based… · p. 13
  • SGBS+EAS significantly outperforms EAS and produces higher-quality solutions than LKH3 on all nine instance sets, while taking more time than LKH3.Its relative gap to HGS ranges from 0.07% on XE 5 to 0.83% on XE 11.Source: A Performance on real-world based… · p. 13

B Implementation of greedy rollouts of SGBS

  • Each simulation phase runs only γ−1 new rollouts per beam node, reusing the redundant rollout result from the previous phase.Thus, it examines β × (γ −1) new candidate solutions per phase.Source: B Implementation of greedy rollouts of… · p. 14

C Search efficiency experiments in Section 3.3

The search-efficiency experiments compare methods under a matched candidate-solution budget, motivated by settings where evaluating a candidate is costly. For SGBS on CVRP n = 100, increasing β and γ improves solution quality, but gains become marginal.

C Search efficiency experiments in Section 3.3

  • The experiments match the number of candidate solutions across search methods to compare how effectively each uses policy information and prior candidate evaluations.This budget-based measure reflects applications where reward or cost evaluations are expensive.Source: C Search efficiency experiments in… · p. 14
  • For CVRP n = 100 and n = 200, the candidate-solution budgets are 1.2K and 2.4K, respectively, matching estimated SGBS rollout counts.With β = 4 and γ = 4, SGBS makes at most 12 new rollouts per simulation phase; the totals are slightly overestimated when few valid next nodes remain.Source: C Search efficiency experiments in… · p. 14
  • The POMO policy is not properly trained to suggest first customer nodes because training manually selects those nodes for diversification.This complicates efficiency comparisons because search methods do not receive a properly trained first-node policy.Source: C Search efficiency experiments in… · p. 15
  • The search baselines receive different starting-node and search procedures: beam search expands from four selected nodes, while MCTS starts from the best one.Sampling, active search, and EAS each generate 0.3K (0.6K) candidates from each of four nodes; beam search uses a beam width of 1.2K (2.4K).Source: C Search efficiency experiments in… · pp. 14–15

D Different sets of (β, γ) for SGBS

  • SGBS’s performance gap drops sharply from greedy, while larger β and γ yield higher-quality solutions with quickly marginal gains.This parameter comparison uses a test set of 10,000 CVRP instances with n = 100; the main-text result uses (β, γ) = (4, 4).Source: D Different sets of (β, γ) for SGBS · p. 15

E Different sets of (β, γ) for SGBS+EAS

On CVRP with 100 nodes, SGBS+EAS performs best among the tested parameter choices at (β, γ) = (4, 4). Across a moderate parameter range, its gap to HGS remains below 0.15%.

E Different sets of (β, γ) for SGBS+EAS

F TSP & CVRP experiments

  • The baseline experiments reuse hyperparameters optimized for n = 100 across problem sizes, so some generalization results may improve with suitable retuning.The reported baselines are run on identical test sets; DACT TSP generalization values are omitted because the results were unsatisfactory.Source: F TSP & CVRP experiments · p. 16

G FFSP experiments

For FFSP experiments, the search methods use a reduced set of eight MatNet instance augmentations for time efficiency. With at least two hours of pre-training, SGBS+EAS finds higher-quality CVRP n = 100 solutions than LKH3 in the reported short-pretraining comparison.

G FFSP experiments

  • For FFSP SGBS(+EAS) experiments and related ablations, MatNet serves as the policy neural-network architecture; models for n = 20, 50, and 100 are trained for 54, 95, and 120 epochs, respectively.Training takes 2, 5, and 35 hours, respectively.Source: G FFSP experiments · p. 16
  • MatNet permits flexible instance augmentation, but the search methods use eight augmentations for time efficiency, selected from the best eight found in a greedy run using 128.The greedy result itself uses ×128 augmentation.Source: G FFSP experiments · pp. 16–17

H Short pre-tain

  • Models with at least 2 hours of pre-training produce CVRP n = 100 solutions of higher quality than LKH3 under SGBS+EAS.The comparison uses 1,000 instances and three-hour SGBS+EAS runs; the paper equates this to a 30-hour run on 10K instances.Source: H Short pre-tain · p. 17

I Early stops and entropy regulation

Greedy CVRP solution quality continues to improve with pretraining, but extended pretraining worsens SGBS+EAS results. Entropy regulation during training and search can mitigate that degradation and improve search quality further.

I Early stops and entropy regulation

Related papers

Loading 2207.06190v3…