Research map / Learning theory and algorithms / Combinatorial and search optimization
Heuristic and local search algorithms
Develops bidirectional, anytime and local search with approximation guarantees.
147 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Combinatorial and search optimization, keyword cluster “planning · search algorithm · tree search”
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.
19 papers in 2023–24 and 33 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic grew, from 5.5% to 9.1%.
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 · Two Efficient Local Search Algorithms for Maximum Weight Clique Problem (AAAI 2016 · 95 citations)
- 2017 · Best-First Width Search: Exploration and Exploitation in Classical Planning (AAAI 2017 · 81 citations)
- 2018 · A Two-Stage MaxSAT Reasoning Approach for the Maximum Weight Clique Problem (AAAI 2018 · 26 citations)
- 2019 · On the Time Complexity of Algorithm Selection Hyper-Heuristics for Multimodal Optimisation (AAAI 2019 · 51 citations)
- 2020 · Real-Time Route Search by Locations (AAAI 2020 · 24 citations)
- 2021 · A Fast Exact Algorithm for the Resource Constrained Shortest Path Problem (AAAI 2021 · 16 citations)
- 2022 · A*+BFHS: A Hybrid Heuristic Search Algorithm (AAAI 2022 · 11 citations)
- 2023 · NuWLS: Improving Local Search for (Weighted) Partial MaxSAT by New Weighting Techniques (AAAI 2023 · 16 citations)
- 2024 · MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encoding (NeurIPS 2024 · 7 citations)
- 2025 · DiverSAT: A Novel and Effective Local Search Algorithm for Diverse SAT Problem (AAAI 2025 · 1 citation)
- 2026 · Theoretical and Empirical Analysis of Lehmer Codes to Search Permutation Spaces with Evolutionary Algorithms (AAAI 2026 · 1 citation)
Earliest papers here
- Two Efficient Local Search Algorithms for Maximum Weight Clique Problem (AAAI 2016 · 95 citations)
- Exponential Recency Weighted Average Branching Heuristic for SAT Solvers (AAAI 2016 · 74 citations)
- Bidirectional Search That Is Guaranteed to Meet in the Middle (AAAI 2016 · 51 citations)
What has been tried
127 papers here report 1,139 measured changes (a component added, removed or swapped, compared with a baseline): helped 67%, no clear effect 9%, hurt 19%, mixed 5%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| add final random projection | MS MARCO · Recall@100 | 77.71 -> 78.82 | Helped | MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encoding (NeurIPS 2024 · 7 citations) |
| add the adaptive perturbation mechanism | hardware, k=100 · diversity quality | 251325612 -> 270244214 | Helped | DiverSAT: A Novel and Effective Local Search Algorithm for Diverse SAT Problem (AAAI 2025 · 1 citation) |
| use nearest-neighbor importance weighting instead of uniform sampling | Small scale · ΔRO (%) | above 1.2% over uniform sampling | Helped | OneBatchPAM: A Fast and Frugal K-Medoids Algorithm (AAAI 2025 · 1 citation) |
| Arrange Zipfian query weights smoothly over space instead of randomly | Synthetic 3D Zipfian distributions · average query depth | Helped | Learning-Augmented Search Data Structures (ICLR 2025 · 1 citation) | |
| increase aspect from 1 to 500 | Pancake problem, unit cost · time to solve | Helped | Rectangle Search: An Anytime Beam Search (AAAI 2024 · 1 citation) | |
| add the weighting strategy in WSA | 26 representative second-category instances · objective value | 20 wins, 4 losses (best); 25 wins, 1 loss (average) | Helped | An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem (AAAI 2025 · 0 citations) |
| Add a weak PDB(12-15) lookup to the strong PDB(0-11) lookup | TOH(22) and TOH(24) · expansions | 413,828 -> 3,861,445; 2,805,473 -> 60,908,811 | Hurt | Anchor Search: A Unified Framework for Suboptimal Bidirectional Search (AAAI 2025 · 0 citations) |
| Normalize AUC and Norm-f across 20 instances before evaluating a configuration | MaxSAT solver configuration · configuration performance | No clear effect | Better Understandings and Configurations in MaxSAT Stochastic Local Search Solvers via Anytime Performance Analysis (AAAI 2025 · 0 citations) | |
| set ϵ from 0 to 0.1 | EPFL stereo faces, k=4 · reconstruction error | 13614 -> 15065 | Hurt | Multi-View Unsupervised Column Subset Selection via Combinatorial Search (Student Abstract) (AAAI 2025 · 0 citations) |
| Replace the octile heuristic with a differential heuristic using 10 pivots | DW Mazes32 · node expansions | Helped | Suboptimal Search with Dynamic Distribution of Suboptimality (AAAI 2025 · 0 citations) | |
| increase diversity parameter m from 1 to 2 | Skewed SIFT · build time | 50 -> 53 | Hurt | Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · 0 citations) |
What reviewers will expect
Datasets and baselines named in the 19 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Baselines
- GBFS · 2 of 19 papers
- Random · 2 of 19 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 52 papers; from OpenAlex and the papers' affiliations).
- Northeast Normal University · 3 papers
- University of Alberta · 3 papers
- Huazhong University of Science and Technology · 2 papers
- Zuse Institute Berlin · 2 papers
- Chinese Academy of Sciences · 2 papers
- Beihang University · 2 papers
- The University of Tokyo · 2 papers
- Alberta Machine Intelligence Institute · 2 papers
- Google DeepMind · 2 papers
- Google · 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
- Classical and HTN planning (145 papers)
- Monte Carlo tree search (55 papers)
- Search for program synthesis (38 papers)
Elsewhere in the topic
- Logic and answer set programming theory (150 papers)
- Unsupervised neural combinatorial optimization (113 papers)
- Constrained neural network optimization (111 papers)
- Decision-focused optimization (97 papers)
- Multi-objective optimization (93 papers)
- Structure and complexity of constraint reasoning (92 papers)
- Predict-then-optimize learning (89 papers)
- SAT and model counting solvers (89 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).