Research map / Reinforcement learning / Visual and representation RL
Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Limited Rollout Beam Search (LRBS), an inference-time beam search with short policy rollouts for DRL 2-opt improvement heuristics on TSP and pickup-delivery TSP, combined with EAS-style offline fine-tuning and online adaptation.
Problem
Generalization of DRL-based improvement heuristics for the Euclidean TSP to much larger instances, where improvement policies have long horizons and existing search methods (SGBS, MCTS) are too costly.
Approach
A beam search for improvement MDPs that expands alpha children per beam node and rolls out the pre-trained policy for n_s steps before selecting the best beta solutions, reducing the effective horizon; combined with EAS adaptation of a small set of new parameters during fine-tuning or online inference.
Key results
- On TSP1000, Ours+OA [5k] reaches 11.89% gap vs 12.04% for Meta-SAGE and 14.54% for Beam Search (from the table); Ours+FT [5k] reaches 11.48%.
- On TSP100, LRBS achieves 0.014% gap, outperforming all listed baselines including POMO (0.078%) and SGBS+EAS (0.024%).
- On PDTSPL500, Ours+OA [3k] reduces the gap to 10.16% versus 148.02% for N2S-A [3k], roughly a 10x reduction.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply LRBS instead of policy sampling | pre-trained improvement policy · TSP500 | optimality gap | Helped |
| Add online adaptation | LRBS · TSP1000 | optimality gap: 20.740% -> 11.889% | Helped |
| Add fine-tuning on a limited set of target-size instances | LRBS · TSP500 | optimality gap: 4.633% -> 3.463% | Helped |
| Remove LRBS from fine-tuning (ablation) | LRBS+FT · TSP200 | optimality gap: 0.50% -> 0.52% | Hurt |
| Remove LRBS from fine-tuning (ablation) | LRBS+FT · TSP500 | optimality gap: 3.46% -> 8.43% | Hurt |
| Remove LRBS from fine-tuning (ablation) | LRBS+FT · TSP1000 | optimality gap: 11.48% -> 81.63% | Hurt |
| Add exploration during fine-tuning instead of sampling from the policy (ablation) | LRBS+FT · TSP200 | optimality gap: 1.44% -> 0.50% | Helped |
| Add exploration during fine-tuning instead of sampling from the policy (ablation) | LRBS+FT · TSP500 | optimality gap: 7.57% -> 3.46% | Helped |
| Add exploration during fine-tuning instead of sampling from the policy (ablation) | LRBS+FT · TSP1000 | optimality gap: 16.06% -> 11.48% | Helped |
| Increase the number of children evaluated per beam node (ablation) | LRBS · TSP500 | optimality gap | Helped |
Surprising findings
- On TSP1000, plain beam search outperforms LRBS, suggesting step-wise selection is better under very large distribution shift.
- Removing LRBS from fine-tuning causes gaps of 81.63% on TSP1000 versus 11.48% with LRBS fine-tuning.
Limitations
- Performance on TSP1000 is inferior to Beam Search without adaptation and not competitive with Meta-SAGE on large instances.
- PDTSP500 results remain far from LKH with gaps well above 50%.
Experimental setup
Datasets: randomly generated Euclidean TSP instances in unit square TSP100 test set from prior work (10,000 instances)
Benchmarks: TSP100 TSP150 TSP200 TSP500 TSP1000 PDTSP200 PDTSP500 PDTSPL200 PDTSPL500
Metrics: optimality gap objective value total runtime
Baselines: POMO SGBS EAS SGBS+EAS DACT A-DACT Costa SGBS+C Beam Search Meta-SAGE N2S-A LKH
Builds on: Efficient Active Search Simulation Guided Beam Search POMO N2S
Closest papers by meaning
- DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems (NeurIPS 2022 · similarity 0.89)
- Combinatorial Optimization with Policy Adaptation using Latent Space Search (NeurIPS 2023 · similarity 0.88)
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.86)
- Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization (ICML 2024 · similarity 0.84)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.84)
- Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.