AI Paper Atlas

Research map / Learning theory and algorithms / Combinatorial and search optimization

Increasing Nogoods in Restart-Based Search

Jimmy Lee, Christian Schulte, Zichen Zhu

AAAI 2016 · Learning theory and algorithms › Combinatorial and search optimization · approach: Heuristic and local search algorithms · 14 citations (OpenAlex)

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 changedWhereMeasuredEffect
record and propagate reduced nld-nogoods across restarts (RST+NG vs RST)restart-based search · Queens Knightsfailures / runtime: 98,055 -> 79,588 failures; 443.28 -> 571.38 s (n=90)Mixed
propagate nogoods with incNGs global constraint (FullFilter) instead of individuallyRST+NG · Queens Knightsruntime (s): 571.38 -> 485.95 (n=90)Improved
use LightFilter with dynamic subscriptions instead of FullFilterRST+NGG · Queens Knightsruntime (s): 485.95 -> 329.53 (n=90)Improved
use LightFilter instead of FullFilterRST+NGG · Open Shop dom/ddegaverage runtime (s): 32.99 -> 3.23 (os-taillard-4)Improved
use LightFilter instead of FullFilterRST+NGG · Open Shop os-taillard-15/20 dom/ddegaverage runtime (s): 2053.33 -> 2192.12 (os-taillard-20)Hurt
use LightFilter instead of RST+NGrestart search · Open Shop dom/wdeg solved instancessolved instances: os-taillard-7: 8/30 -> 11/30Improved
add approximate nogood shortening to LightFilter (ablation)RST+NGLG · Queens Knightsfailures: 79,588 -> 43,246 (n=90)Improved
approximate shortening instead of exact minimal nogoods (ablation)RST+NGM · Queens Knightsfailures: 43,067 vs 43,246 (n=90)No clear effect
add shortening/minimization to nogoods (ablation)RST+NGLG · Open Shop dom/wdegsolved instances: os-taillard-10: 9/30 -> 18/30; os-taillard-20: 17/30 -> 16/30Mixed
exact minimal nogoods instead of shortened nogoods (ablation)RST+NGLG · Open Shop os-taillard-7 dom/wdegsolved instances: 12/30 -> 14/30Improved
add minimal or shortened nogoods (ablation)RST+NG · RLFAP dom/wdegperformanceNo clear effect

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy