Research map / Learning theory and algorithms / Combinatorial and search optimization
Unsupervised neural combinatorial optimization
Learns solvers for combinatorial problems via unsupervised relaxation, divide-and-conquer and learned branching.
113 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Combinatorial and search optimization, keyword cluster “objective · multi · solutions”
State History Tried Checklist Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
34 papers in 2023–24 and 35 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic held steady, from 9.8% to 9.6%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Solving the Station Repacking Problem (AAAI 2016 · 18 citations)
- 2017 · Maximizing the Probability of Arriving on Time: A Practical Q-Learning Method (AAAI 2017 · 53 citations)
- 2018 · Greedy Hash: Towards Fast Optimization for Accurate Hash Coding in CNN (NeurIPS 2018 · 123 citations)
- 2019 · CapsAndRuns: An Improved Method for Approximately Optimal Algorithm Configuration (ICML 2019 · 16 citations)
- 2020 · A Learning-based Iterative Method for Solving Vehicle Routing Problems (ICLR 2020 · 123 citations)
- 2021 · Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization (AAAI 2021 · 127 citations)
- 2022 · Learning to Solve Travelling Salesman Problem with Hardness-Adaptive Curriculum (AAAI 2022 · 34 citations)
- 2023 · Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization (NeurIPS 2023 · 24 citations)
- 2024 · NN-Steiner: A Mixed Neural-Algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem (AAAI 2024 · 11 citations)
- 2025 · DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · 7 citations)
- 2026 · UCPO: A Universal Constrained Combinatorial Optimization Method via Preference Optimization (AAAI 2026 · 2 citations)
Earliest papers here
- Solving the Station Repacking Problem (AAAI 2016 · 18 citations)
- A Box-Constrained Approach for Hard Permutation Problems (ICML 2016 · 7 citations)
- Maximizing the Probability of Arriving on Time: A Practical Q-Learning Method (AAAI 2017 · 53 citations)
What has been tried
86 papers here report 725 measured changes (a component added, removed or swapped, compared with a baseline): helped 70%, no clear effect 7%, hurt 17%, mixed 6%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Add cell/subtree refinement steps to NN-Steiner tree construction (vs. none) | Uniform pointsets, 500-5000 points · avg % length diff vs FLUTE | refinement contributes most; e.g. 500 pts: 3.39 without cell refinement, 0.39 without subtree refinement, -0.67 full | Helped | NN-Steiner: A Mixed Neural-Algorithmic Approach for the Rectilinear Steiner Minimum Tree Problem (AAAI 2024 · 11 citations) |
| use POMO instead of ICAM as the conquering policy | TSP500 · optimality gap | 2.54% vs 2.64% (x2); 1.58% vs 1.64% (x50) | No clear effect | UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems (NeurIPS 2024 · 10 citations) |
| add path-based divide-and-optimize to the grid-based method | TSP_random · Obj. | 23.34 -> 23.31 (TSP1K); 234.2 -> 230.83 (TSP100K) | Helped | DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem (AAAI 2025 · 7 citations) |
| Use ranking loss instead of classification loss | Synthetic TSP · optimality gap | 1.94% -> 1.86% | Helped | Neural Solver Selection for Combinatorial Optimization (ICML 2025 · 1 citation) |
| Train across capacities from 10 to 500 and add the multi-expert module | CVRP100 varying capacities · average optimality gap | 10.78% -> 1.86% | Helped | Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees (NeurIPS 2025 · 1 citation) |
| Add preference learning instead of REINFORCE | Bi-TSP100 · convergence speed | Helped | Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation (NeurIPS 2025 · 1 citation) | |
| Increase α when predictions are accurate; decrease α when predictions are bad | Steiner Tree · solution cost | Mixed | Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · 1 citation) | |
| Provide previous machine assignments as warm-start hints rather than fixing operations | FJSP start delay, 1050 operations · TI % | -12.9% ± 1.6% | Hurt | Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling (ICLR 2025 · 1 citation) |
| use PolyNet's learned strategies instead of forced first actions | TSP, CVRP, and CVRPTW, n=100 · Gap | 0.006% -> 0.000%; 0.59% -> 0.49%; 3.00% -> 2.73% | Helped | PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization (ICLR 2025 · 1 citation) |
| Adapt cascade ordering to updated instance features rather than keep it static | MINTW test set, 7800s timeout · TΣ | 728 -> 712 | Hurt | SAT-Based Tree Decomposition with Iterative Cascading Policy Selection (AAAI 2024 · 1 citation) |
| Encode upper and lower bound matrices separately and sum their node embeddings rather than blend the matrices | R-40-100 · Obj | 8.0640 -> 7.9610; 7.9095 -> 7.8985; 7.8760 -> 7.8600 | Helped | Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times (NeurIPS 2024 · 1 citation) |
| Remove pre-training from ROS | Random regular graphs · cut value | 128.20 (± 2.82) -> 132.80 (± 1.99); 240.30 (± 2.59) -> 243.20 (± 1.80) | Helped | ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · 0 citations) |
What reviewers will expect
Datasets and baselines named in the 26 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Baselines
- Concorde · 3 of 26 papers
- POMO · 3 of 26 papers
- DIFUSCO · 3 of 26 papers
- LEHD · 3 of 26 papers
- LKH3 · 2 of 26 papers
- DIMES · 2 of 26 papers
- Gurobi · 2 of 26 papers
- MatNet · 2 of 26 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 69 papers; from OpenAlex and the papers' affiliations).
- Shanghai Jiao Tong University · 3 papers
- Google · 3 papers
- Sun Yat-sen University · 3 papers
- Southern University of Science and Technology · 3 papers
- Massachusetts Institute of Technology · 3 papers
- Hokkaido University · 2 papers
- University of California, San Diego · 2 papers
- University of Michigan · 2 papers
- Huazhong University of Science and Technology · 2 papers
- Singapore Management University · 2 papers
Use it
Download BibTeX of 40 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Constrained neural network optimization (111 papers)
- Decision-focused optimization (97 papers)
- Multi-objective optimization (93 papers)
- Globally optimal geometric optimization (56 papers)
Elsewhere in the topic
- Logic and answer set programming theory (150 papers)
- Heuristic and local search algorithms (147 papers)
- Classical and HTN planning (145 papers)
- Structure and complexity of constraint reasoning (92 papers)
- Predict-then-optimize learning (89 papers)
- SAT and model counting solvers (89 papers)
- Heuristics for integer programming (60 papers)
- Differentiable and symbolic reasoning (56 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).