Integer linear programming achieves provably optimal solutions up to 19 × 19 grids for the classic No-Three-In-Line problem, outperforming artificial intelligence methods in both solution quality and scalability. In a comparative evaluation examining classical mathematical solvers alongside modern deep learning frameworks, the classical optimization approach successfully resolved large geometric instances that caused neural network methods to degrade or violate core problem constraints.
The No-Three-In-Line problem is a renowned challenge in combinatorial geometry and constraint satisfaction that asks for the maximum number of points that can be placed on an n × n grid such that no three points are collinear. Because every additional grid point introduces multiple geometric relationships that must be evaluated across all possible lines, identifying valid placements becomes exceptionally difficult as the dimensions of the grid increase.
The study was conducted by researchers Thomas Prellberg, Pranav Ramanathan, and Matthew James Lewis from Queen Mary University of London in the United Kingdom, alongside Prathamesh Dinesh Joshi, Raj Abhijit Dandekar, Rajat Dandekar, and Sreedath Panat from Vizuara AI Labs in Pune, India. Their research, published in Frontiers in Artificial Intelligence within the Machine Learning section, directly compared classical optimization techniques with modern machine learning paradigms on identical benchmark conditions.
To evaluate how modern computational approaches handle rigorous geometric constraints, the authors benchmarked three specific techniques. These comprised classical integer linear programming utilizing the Gurobi optimization solver, a transformer-based pattern learning approach designated as PatternBoost, and a reinforcement learning model operating through proximal policy optimization.
Among the learning-based systems, the transformer-driven PatternBoost framework showed the strongest capability for matching exact mathematical solutions on smaller configurations. The model successfully matched optimal performance up to 14 × 14 grids, but its accuracy declined slightly on larger boards; on a 15 × 15 grid, PatternBoost managed to place 29 valid points, just one point below the provably optimal solution of 30 points.
In contrast, the reinforcement learning implementation using proximal policy optimization encountered strict performance limits earlier in the scaling process. Although the proximal policy optimization agent achieved perfect solutions on 10 × 10 grids, it failed completely on 11 × 11 grids due to unavoidable constraint violations, highlighting the ongoing challenge reinforcement learning faces when navigating strict, non-negotiable geometric rules.
The experimental protocol also assessed algorithmic reliability across four separate fixed-timeout runs to determine performance stability. In these multi-run trials, integer linear programming remained consistently reliable through grid sizes of n = 17, while PatternBoost maintained reliability through n = 12. Proximal policy optimization demonstrated the lowest consistency, succeeding only once at a grid size of n = 10 across the repeated trials.
Based on their empirical comparison, the authors concluded that classical optimization remains indispensable for obtaining exact, provably optimal solutions in combinatorial geometry, while artificial intelligence techniques provide competitive performance primarily on smaller instances. The researchers noted that hybrid approaches integrating exact mathematical solvers with learned heuristics appear to be the most promising direction for scaling solutions to larger grid instances.
Subject of Research: Computational approaches to the No-Three-In-Line problem
Article Title: Three methods, one problem: classical and AI approaches to no-three-in-line
Article References: Ramanathan, P., Prellberg, T., Lewis, M. J., Beck, C., Joshi, P. D., Dandekar, R. A., Dandekar, R., & Panat, S. (2026). Three methods, one problem: classical and AI approaches to no-three-in-line. Frontiers in Artificial Intelligence, 9, Article 1799444. https://doi.org/10.3389/frai.2026.1799444
Image Credits: AI Generated
DOI: 10.3389/frai.2026.1799444
Keywords: No-Three-In-Line problem, combinatorial geometry, integer linear programming, Gurobi solver, PatternBoost, transformer models, reinforcement learning, proximal policy optimization, combinatorial optimization, constraint satisfaction, grid configurations, exact optimization, learned heuristics, collinear points, hybrid optimization, constraint violations, fixed-timeout evaluations
Cite Scienmag News
Denise Maddox. (November 17, 2026). Integer Linear Programming Finds Provably Optimal Solutions Up to 19×19 Grids. Scienmag. https://scienmag.com/integer-linear-programming-finds-provably-optimal-solutions-up-to-19x19-grids/
Denise Maddox. "Integer Linear Programming Finds Provably Optimal Solutions Up to 19×19 Grids." Scienmag, 17 November 2026, https://scienmag.com/integer-linear-programming-finds-provably-optimal-solutions-up-to-19x19-grids/. Accessed 17 November 2026.
Denise Maddox. "Integer Linear Programming Finds Provably Optimal Solutions Up to 19×19 Grids." Scienmag. November 17, 2026. https://scienmag.com/integer-linear-programming-finds-provably-optimal-solutions-up-to-19x19-grids/








