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.

通过引入模拟指导波束搜索（SGBS）和有效主动搜索（EAS）的组合，提高了神经组合优化的搜索效率。