From Global Optimization to Exact Coordinates: Heilbronn's Triangle Problem on the Unit Square Using Mixed-Integer Nonlinear Optimization

Abstract

We develop a mixed-integer nonlinear programming (MINLP) approach for the Heilbronn triangle problem on the unit square. The formulation exploits the boundary structure of optimal configurations, which we establish rigorously, to fix coordinates and orientation variables a priori. With this formulation, a general-purpose global solver solves the case $n=9$ to global optimality within its numerical tolerances in about eight minutes on a laptop and without any precomputation, compared with about 23 hours of total computation for the best previous approach. The same model also solves $n=10$ for the first time, in under seven hours, and confirms the configuration of Comellas and Yebra (2002). The numerical solutions then guide an exact symbolic reconstruction, and the minimum triangle area of every reconstructed configuration is verified in exact arithmetic. This yields exact coordinates for all $n\le 10$, including the configurations of Comellas and Yebra (2002) for $n=9$ and $n=10$, together with rigorous lower bounds. Finally, we derive structural properties of optimal configurations, formulate a conjecture on the number of critical triangles, and pose an open question. All code and data are publicly available.

arXiv comment31 pages, 9 figures, 16 tables. Revised version, submitted to Mathematical Programming Computation. v3: new title, n=10 solved, revised status of results. Code and data: https://github.com/spiralulam/heilbronn