Benchmark compares classical and AI searches for geometry problems
RadonBench: A Benchmark of Classical and Learning-Guided Search Techniques for Problems in Combinatorial Geometry
Machine Learning
Summary
Finding special sets of points in grids without certain patterns is a tricky math puzzle. The authors created a benchmark called RadonBench to test different search methods, including traditional and AI-based ones, on this problem. They found that none of the tested methods could fully solve the hardest cases but could get very close. This helps show where current approaches stand for solving these kinds of geometry puzzles.
What this means in practice
- •For optimization engineers: Use RadonBench to evaluate and compare search techniques when designing algorithms for complex discrete geometry problems.
- •For ai algorithm developers: Employ RadonBench as a testbed to develop and benchmark learning-guided search methods targeting combinatorial optimization challenges.
Authors
Xiaoan Xu, Ethan X. Fang, Jesus A. De Loera, Junwei Lu, Luze Xu
Abstract
Classical optimization and learning-guided search offer complementary approaches to open problems in discrete mathematics, but their outputs are difficult to compare when search spaces, validity checks, and stopping rules differ. We present \emph{RadonBench}, a benchmark for constructing maximum-cardinality Radon-free lattice configurations: finite subsets of $\mathbb{Z}^d$ admitting no integral Radon partition. It remains open whether Radon-free configurations with $11$ points in $\mathbb{Z}^3$ or $21$ points in $\mathbb{Z}^4$ are possible. If they exist, they would improve the corresponding lower bounds on the integer Radon numbers. We compare exhaustive extension, greedy local search, PatternBoost, AlphaZero, and AlphaEvolve. All outputs use one success predicate: a convex target-sized configuration succeeds exactly when its number of integral Radon points is zero. PatternBoost and AlphaZero construct verified Radon-free configurations of sizes $10$ and $20$, one point short of the respective targets; AlphaZero's best convex target terminals have two integral Radon points in both dimensions. Exhaustive extension over fixed seeds and declared finite search boxes likewise reaches a minimum of two integral Radon points. Greedy local search and AlphaEvolve each produce target-sized near misses with one integral Radon point. No audited run reaches zero. These results establish reproducible near-miss baselines over explicitly scoped search domains.