Three methods, one problem: Classical and AI approaches to no-three-in-line
This addresses a combinatorial geometry problem for researchers in optimization and AI, offering incremental insights by comparing classical and AI approaches for the first time.
The paper tackled the No-Three-In-Line problem by comparing classical Integer Linear Programming (ILP) with AI methods like PatternBoost transformer learning and reinforcement learning (PPO), finding that ILP achieves optimal solutions up to 19x19 grids, PatternBoost matches optimal performance up to 14x14 grids with 96% test loss reduction, and PPO works perfectly on 10x10 grids but fails on 11x11 grids.
The No-Three-In-Line problem asks for the maximum number of points that can be placed on an n by n grid with no three collinear, representing a famous problem in combinatorial geometry. While classical methods like Integer Linear Programming (ILP) guarantee optimal solutions, they face exponential scaling with grid size, and recent advances in machine learning offer promising alternatives for pattern-based approximation. This paper presents the first systematic comparison of classical optimization and AI approaches to this problem, evaluating their performance against traditional algorithms. We apply PatternBoost transformer learning and reinforcement learning (PPO) to this problem for the first time, comparing them against ILP. ILP achieves provably optimal solutions up to 19 by 19 grids, while PatternBoost matches optimal performance up to 14 by 14 grids with 96% test loss reduction. PPO achieves perfect solutions on 10 by 10 grids but fails at 11 by 11 grids, where constraint violations prevent valid configurations. These results demonstrate that classical optimization remains essential for exact solutions while AI methods offer competitive performance on smaller instances, with hybrid approaches presenting the most promising direction for scaling to larger problem sizes.