From Global Optimization to Exact Coordinates: Heilbronn's Triangle Problem on the Unit Square Using Mixed-Integer Nonlinear Optimization
math.OC, math.CO
Submitted: 2026-03-11
Updated: 2026-10-27
Comments: 31 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
Code: https://github.com/spiralulam/heilbronn
License: http://creativecommons.org/licenses/by/4.0/
The gist: We develop a mixed-integer nonlinear programming (MINLP) approach for the Heilbronn triangle problem on the unit square.
Terminology
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 at most 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.
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise