Research map / Reinforcement learning / MDPs and planning
BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BQ-MDP policies instead of end-to-end constructive baselines | TSP · TSP N=1000 | optimality gap: 29.75% -> 2.29% | Helped |
| Use BQ-MDP policies instead of end-to-end constructive baselines | CVRP · CVRP N=1000 | optimality gap: 86.41% -> 5.88% | Helped |
| Use beam search size 16 instead of greedy decoding | BQ-transformer · TSP N=1000 | optimality gap: 2.29% -> 1.38% | Helped |
| Replace the transformer with PerceiverIO (ablation) | BQ policy · TSP N=1000 | optimality gap: 2.29% -> 8.97% | Hurt |
| Recompute the entire model after each construction step instead of only the top layer (ablation) | BQ-transformer · TSP100 | optimality gap: 8.175% -> 0.35% | Helped |
| Restrict candidate nodes to 250 nearest neighbors (ablation) | BQ-transformer greedy · CVRP N=1000 | optimality gap: 6.282% -> 5.883% | Helped |
| Restrict candidate nodes to 250 nearest neighbors (ablation) | BQ-transformer greedy · TSP N=1000 | inference time: 14m -> 2m | Helped |
| Sort expert CVRP subtours by remaining vehicle capacity (ablation) | CVRP imitation training · CVRP | performance | Helped |
| Train on expert trajectories with subtours in arbitrary order (ablation) | CVRP imitation training · CVRP | performance | Hurt |
| Apply beam search rather than greedy decoding | BQ-transformer · OP N=1000 | optimality gap: 13.12% -> 10.69% | Helped |
| Use BQ greedy rather than POMO all trajectories | Knapsack policy · KP All | optimality gap: 4.647% -> 0.516% | Helped |
Closest papers by meaning
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.90)
- BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization (ICML 2025 · similarity 0.89)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.89)
- Learning to Insert for Constructive Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.88)
- Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (NeurIPS 2025 · similarity 0.88)
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.87)
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.