Combining a constructive proof with systematic empirical validation shows that some hard optimization problems resist heuristic improvements—the paper demonstrates both the solution and why current search methods hit a fundamental barrier.
This paper solves the 20-year-old frb100-40 benchmark by finding a 100-vertex independent set in a 4,000-vertex graph, proving the maximum independent set is exactly 100. The authors also conduct a rigorous preregistered study testing whether new repair operators improve search performance, finding no statistically significant speedup over existing methods.