Research map / Learning theory and algorithms / Combinatorial and search optimization
Neural Solver Selection for Combinatorial Optimization
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 a framework that selects, per instance, which of several open-source neural solvers to run for TSP and CVRP, using a graph-attention/hierarchical encoder and a classification or ranking selection model with greedy, top-k, rejection, or top-p strategies.
Problem
Existing neural solvers for combinatorial optimization show complementary performance across instances, yet no single solver dominates, and running all solvers per instance is costly.
Approach
Instance-level selection among a zoo of existing neural solvers, using a learned selection model (trained with a Plackett-Luce-style ranking loss or classification loss on solver objectives) plus confidence-based multi-solver strategies, so only the selected solvers run at inference.
Key results
- Ranking model with top-k (k=2) selection reaches 1.51% gap on synthetic TSP vs 2.33% for best single solver DIFUSCO (Oracle 1.24%).
- On TSPLIB the ranking model with top-k selection reduces gap from 1.95% (T2T) to 1.07%, a 0.88% improvement.
- On CVRPLIB Set-X, top-k ranking selection achieves 5.39% vs 6.10% for best single solver ELG, a 0.71% improvement.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Coordinate instance-specific solver selection rather than use the best single solver | Neural solver selection framework · Synthetic TSP | optimality gap: 2.33% -> 1.51% | Helped |
| Coordinate instance-specific solver selection rather than use the best single solver | Neural solver selection framework · Synthetic CVRP | optimality gap: 6.82% -> 4.81% | Helped |
| Use ranking loss instead of classification loss (ablation) | Solver selection model with greedy selection · Synthetic TSP | optimality gap: 1.94% -> 1.86% | Helped |
| Use ranking loss instead of classification loss (ablation) | Solver selection model with greedy selection · Synthetic CVRP | optimality gap: 5.35% -> 5.31% | Helped |
| Select top-2 solvers instead of greedy selection (ablation) | Ranking-based solver selection · Synthetic TSP | optimality gap: 1.86% -> 1.51% | Helped |
| Select top-2 solvers instead of greedy selection (ablation) | Ranking-based solver selection · Synthetic CVRP | optimality gap: 5.31% -> 4.82% | Helped |
| Use graph attention features instead of manual features (ablation) | Ranking-based greedy selection · Synthetic TSP | optimality gap: 1.97% -> 1.87% | Helped |
| Use graph attention features instead of manual features (ablation) | Ranking-based greedy selection · Synthetic CVRP | optimality gap: 5.49% -> 5.30% | Helped |
| Add hierarchical graph pooling to the attention encoder (ablation) | Ranking-based greedy selection · TSPLIB | optimality gap: 1.45% -> 1.33% | Helped |
| Add hierarchical graph pooling to the attention encoder (ablation) | Ranking-based greedy selection · CVRPLIB Set-X | optimality gap: 5.87% -> 5.76% | Helped |
| Add hierarchical graph pooling to the attention encoder (ablation) | Ranking-based greedy selection · CVRP | optimality gap: 5.30% -> 5.31% | Hurt |
| Aggregate multi-layer features without graph pooling instead of using hierarchical graph pooling (ablation) | Hierarchical graph encoder · CVRPLIB Set-X | optimality gap: 5.86% -> 5.76% | Hurt |
Surprising findings
- Greedy selection with the ranking model is about as fast as a single solver while already beating the best individual solver on TSP (1.86% vs 2.33%).
Limitations
- Solver zoo is fixed; selection uses fixed solver indices and cannot directly handle newly added solvers without the preliminary solver-feature extension.
- Assumes solver runtimes are short; runtime-aware selection is not handled for time-consuming learn-to-search solvers.
- Selection accuracy is modest (about 35-62%), so greedy selection leaves a gap to the Oracle.
Experimental setup
Datasets: synthetic TSP (Gaussian mixture, N in [50,500]) synthetic CVRP (Gaussian mixture, N in [50,500])
Benchmarks: synthetic TSP synthetic CVRP TSPLIB CVRPLIB Set-X
Metrics: optimality gap average time selection accuracy
Baselines: Omni BQ LEHD DIFUSCO T2T ELG INViT MVMoE Oracle salesperson-based algorithm selection
Builds on: graph attention network Poppy algorithm selection ReZero
Closest papers by meaning
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.91)
- CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention (ICML 2025 · similarity 0.90)
- Learning to Insert for Constructive Neural Vehicle Routing Solver (NeurIPS 2025 · similarity 0.90)
- Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (NeurIPS 2025 · similarity 0.90)
- Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · similarity 0.89)
- Memory-Enhanced Neural Solvers for Routing Problems (NeurIPS 2025 · similarity 0.89)
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.