Research map / Probabilistic and scientific modeling / Bayesian optimization
Learning Encodings for Constructive Neural Combinatorial Optimization Needs to Regret
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 LCH-Regret, a model-agnostic plug-in that adds a learnable regret encoding and regret operation (roll back one node) to autoregressive learning constructive heuristics, improving POMO, AM and MatNet on TSP, CVRP and FFSP.
Problem
Learning constructive heuristics for neural combinatorial optimization converge slowly and leave a gap to optimal solutions because the autoregressive greedy construction process is unchanged and can get stuck in local optima.
Approach
Introduce a regret operation that lets the policy erase the last selected node during construction, modeled as a virtual learnable regret token alongside candidate nodes, trained with an added REINFORCE loss term on regret actions so it can be plugged into any LCH model.
Key results
- POMO-Regret with x8 augmentation reaches 0.02% gap on TSP50 and 0.11% on TSP100 versus POMO-8 aug at 0.03% and 0.13%.
- AM-Regret reduces the CVRP100 gap from 7.58% (AM) to 6.92%, and POMO-Regret reduces the CVRP100 gap from 2.17% to 2.08% (no augmentation).
- MatNet-Regret with x128 augmentation achieves gaps of 0.1%/-/0.4% area comparable to MatNet on FFSP, improving FFSP50 from 0.2% to... (table reports MatNet-Regret-128 aug cost 49.4 vs MatNet-128 aug 49.6 on FFSP50).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add the LCH-Regret mechanism to POMO with ×8 augmentation | POMO · TSP50, uniform | average solution cost: 5.6919 -> 5.6916 | Helped |
| Add the LCH-Regret mechanism to POMO with ×8 augmentation | POMO · TSP100, uniform | average solution cost: 7.7711 -> 7.7697 | Helped |
| Add the LCH-Regret mechanism to AM | AM · TSP50, uniform | average solution cost: 5.8003 -> 5.7946 | Helped |
| Add the LCH-Regret mechanism to AM | AM · TSP100, uniform | average solution cost: 8.1029 -> 8.0927 | Helped |
| Add the LCH-Regret mechanism to POMO with ×8 augmentation | POMO · CVRP50, uniform | average solution cost: 10.4577 -> 10.4526 | Helped |
| Add the LCH-Regret mechanism to POMO with ×8 augmentation | POMO · CVRP100, uniform | average solution cost: 15.7863 -> 15.7755 | Helped |
| Add the LCH-Regret mechanism to AM | AM · CVRP50, uniform | average solution cost: 11.0330 -> 10.9785 | Helped |
| Add the LCH-Regret mechanism to AM | AM · CVRP100, uniform | average solution cost: 16.7566 -> 16.6543 | Helped |
| Add the LCH-Regret mechanism to POMO | POMO · TSP100, uniform | optimal gap: 0.37% -> 0.33% | Helped |
| Add the LCH-Regret mechanism to POMO | POMO · TSP150, cluster | optimal gap: 5.76% -> 4.91% | Helped |
| Add the LCH-Regret mechanism to POMO | POMO · TSP200, mixed | optimal gap: 7.17% -> 4.71% | Helped |
| Add the LCH-Regret mechanism to MatNet with ×128 augmentation | MatNet · FFSP20 | average solution cost: 25.4 -> 25.3 | Helped |
Surprising findings
- The regret mechanism is only used in training; testing disables regret operations, which the authors say generalizes better.
Limitations
- Regret mask rules are hand-designed and differ for CVRP, requiring problem-specific rules
- Only one-step regret is studied
- LCH-Regret slightly increases running time
Experimental setup
Datasets: uniform random TSP instances uniform random CVRP instances FFSP instances
Benchmarks: TSP50 TSP100 CVRP50 CVRP100 TSPlib FFSP20 FFSP50 FFSP100 TSP clustered/mixed generalization sets
Metrics: optimal gap average cost inference time
Baselines: AM POMO RL-CSL Sym-NCO MDAM MatNet Concorde LKH3 OR Tools HGS Shortest Job First Genetic Algorithm
Builds on: POMO Attention Model MatNet REINFORCE
Closest papers by meaning
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.87)
- Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization (ICML 2025 · similarity 0.86)
- Probing Neural Combinatorial Optimization Models (NeurIPS 2025 · similarity 0.85)
- BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization (ICML 2025 · similarity 0.85)
- Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization (ICML 2024 · similarity 0.85)
- PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization (ICLR 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.