Research map / Learning theory and algorithms / Combinatorial and search optimization
Increasing Nogoods in Restart-Based Search
Jimmy Lee, Christian Schulte, Zichen Zhu
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| record and propagate reduced nld-nogoods across restarts (RST+NG vs RST) | restart-based search · Queens Knights | failures / runtime: 98,055 -> 79,588 failures; 443.28 -> 571.38 s (n=90) | Mixed |
| propagate nogoods with incNGs global constraint (FullFilter) instead of individually | RST+NG · Queens Knights | runtime (s): 571.38 -> 485.95 (n=90) | Improved |
| use LightFilter with dynamic subscriptions instead of FullFilter | RST+NGG · Queens Knights | runtime (s): 485.95 -> 329.53 (n=90) | Improved |
| use LightFilter instead of FullFilter | RST+NGG · Open Shop dom/ddeg | average runtime (s): 32.99 -> 3.23 (os-taillard-4) | Improved |
| use LightFilter instead of FullFilter | RST+NGG · Open Shop os-taillard-15/20 dom/ddeg | average runtime (s): 2053.33 -> 2192.12 (os-taillard-20) | Hurt |
| use LightFilter instead of RST+NG | restart search · Open Shop dom/wdeg solved instances | solved instances: os-taillard-7: 8/30 -> 11/30 | Improved |
| add approximate nogood shortening to LightFilter (ablation) | RST+NGLG · Queens Knights | failures: 79,588 -> 43,246 (n=90) | Improved |
| approximate shortening instead of exact minimal nogoods (ablation) | RST+NGM · Queens Knights | failures: 43,067 vs 43,246 (n=90) | No clear effect |
| add shortening/minimization to nogoods (ablation) | RST+NGLG · Open Shop dom/wdeg | solved instances: os-taillard-10: 9/30 -> 18/30; os-taillard-20: 17/30 -> 16/30 | Mixed |
| exact minimal nogoods instead of shortened nogoods (ablation) | RST+NGLG · Open Shop os-taillard-7 dom/wdeg | solved instances: 12/30 -> 14/30 | Improved |
| add minimal or shortened nogoods (ablation) | RST+NG · RLFAP dom/wdeg | performance | No clear effect |
Closest papers by meaning
- Towards More Practical and Efficient Automatic Dominance Breaking (AAAI 2021 · similarity 0.83)
- Enriching Non-Parametric Bidirectional Search Algorithms (AAAI 2019 · similarity 0.82)
- Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search (NeurIPS 2025 · similarity 0.80)
- Adaptive Hardness Negative Sampling for Collaborative Filtering (AAAI 2024 · similarity 0.80)
- Online Weighted Paging with Unknown Weights (NeurIPS 2024 · similarity 0.80)
- Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks (AAAI 2025 · similarity 0.80)
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.
