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

Each language version is independently generated for its own context, not a direct translation.

这篇文章讲述了一个非常有趣的数学谜题，叫做**“海尔布隆三角形问题”（Heilbronn Triangle Problem）**。

想象一下，你有一块正方形的蛋糕（单位正方形），你需要在上面切出 $n$ 个点。你的目标是：无论你怎么切，这三个点连成的三角形面积，都要尽可能大。

听起来有点反直觉？通常我们想避免三角形太小，但这里的问题是：怎么摆放这些点，才能让最小的那个三角形变得最大？就像是在玩一个“让最小的缝隙尽可能宽”的游戏。

这篇论文就像是一位**“数学侦探”**，用一种全新的、更聪明的方法，不仅解决了这个老难题，还给出了精确到小数点后无数位的完美答案。

以下是用大白话和比喻对这篇论文核心内容的解读：

1. 以前的困难：在迷宫里找出口

以前，数学家们想解决这个问题，就像是在一个巨大的、充满死胡同的迷宫里找出口。

迷宫太大：点的排列组合多到数不清（比如 9 个点就有几百万种对称的摆法）。
计算太慢：以前的超级计算机跑这个题目，可能需要跑整整一天甚至更久，而且有时候只能算出个“大概”，不敢保证是“绝对完美”的。
之前的记录：对于 9 个点的情况，之前的研究花了大约一天时间才勉强算出结果。

2. 新武器：优化 + 精炼（先猜后证）

作者发明了一套"先优化，后精炼"（Optimize-then-Refine）的绝招，分两步走：

第一步：用“智能导航”快速定位（混合整数优化）

作者设计了一个超级聪明的数学模型，就像给迷宫装上了**“智能导航”**。

打破对称性（Symmetry Breaking）：这是最关键的一步。想象一下，如果你把蛋糕旋转 90 度，或者左右翻转，点的相对位置其实没变。以前的计算机会傻傻地把这些“旋转后的相同情况”都算一遍。
- 作者的做法：直接规定“第一个点必须在左边，第二个点必须在底边……"。就像规定“进迷宫必须先走左边那条路”，一下子就把几百万种重复的路线砍掉了，只留下唯一的一条路。
结果：原本需要跑一天的任务，现在在普通家用电脑上，15 分钟就搞定了！而且计算机不仅给出了答案，还盖上了“全球最优”的认证印章，保证没有更好的解了。

第二步：用“显微镜”看清细节（精确符号计算）

计算机算出来的数字是“近似值”（比如 0.5839...），虽然很准，但数学家想要的是**“精确值”**（比如 $\frac{\sqrt{65}}{10}$ 这种带根号的完美分数）。

作者的做法：利用第一步算出的“大概位置”，推测出哪些点是关键的（比如哪些点在边缘，哪些三角形面积最小）。然后，把这些线索变成一组精确的方程，用代数软件（像 SymPy）去解。
结果：就像用显微镜看清了 DNA 序列一样，作者得到了所有点的精确坐标。以前别人猜出来的答案，现在被证实是完美的，而且公式变得更简洁、更漂亮了。

3. 发现了什么新秘密？

在解出 $n=5$ 到 $n=9$ 的所有完美答案后，作者发现了一些有趣的**“几何规律”**：

临界三角形的数量在增加：随着点的数量增加，那些“最小面积”的三角形（也就是决定胜负的关键三角形）数量也在变多。这就像是在玩拼图，拼图块越多，边缘的卡扣（关键约束）就越多。
非关键三角形的“抱团”现象：除了那些最小的三角形，剩下的大三角形面积并不是杂乱无章的，而是聚集成几个特定的数值。
- 比喻：想象你在一个房间里放气球。最小的气球（关键三角形）大小都一样。剩下的气球（非关键三角形）虽然比最小的大，但它们的大小并不是随意分布的，而是像排队一样，整齐地分成几组（比如有的刚好是 0.1，有的刚好是 0.2）。
- 这暗示了这些点的排列有着某种深层的、隐藏的秩序，就像晶体结构一样整齐。

4. 为什么这很重要？

速度提升：把计算时间从“一天”缩短到"15 分钟”，效率提升了 10 倍以上。
数学证明：这是第一次严格证明了 9 个点的最佳摆法是完美的，并且给出了所有点的精确坐标。
新方向：这种“先算大概，再求精确”的方法，不仅可以用来切蛋糕（摆点），还可以用来解决其他复杂的几何问题，比如怎么最有效地堆放货物、设计芯片布局等。

总结

这就好比以前我们想找到宝藏，只能拿着地图在森林里盲目乱撞，花了一整天才找到大概位置。
现在，作者发明了一种**“魔法罗盘”（新的数学模型），能瞬间锁定宝藏的大致位置；然后拿出一把“精密手术刀”**（符号计算），把宝藏的坐标精确到微米级别，并发现宝藏周围还藏着某种神秘的几何规律。

这篇论文不仅解决了 9 个点的老大难问题，还为未来解决更复杂（比如 10 个点、100 个点）的几何谜题打开了一扇新的大门。所有的代码和答案都公开了，就像把藏宝图分享给了全世界。

Each language version is independently generated for its own context, not a direct translation.

这是一份关于论文《从计算认证到精确坐标：基于混合整数优化的单位正方形海因布伦三角形问题》（From Computational Certification to Exact Coordinates: Heilbronn's Triangle Problem on the Unit Square Using Mixed-Integer Optimization）的详细技术总结。

1. 问题背景 (The Problem)

海因布伦三角形问题 (Heilbronn Triangle Problem) 是离散几何中的一个经典问题。其核心目标是：
在单位正方形 $[0, 1]^2$ 内放置 $n$ 个点，使得由任意三点构成的三角形中，面积最小的那个三角形的面积尽可能大。

符号定义：设 $\Delta_n$ 为 $n$ 个点的最优配置下最小三角形的面积。
历史背景：该问题由汉斯·海因布伦 (Hans Heilbronn) 提出。他猜想 $\Delta_n = O(1/n^2)$ ，但这后来被证明是不正确的（下界实际上约为 $\Omega(\log n / n^2)$ ）。
研究现状：对于较小的 $n$ （如 $n \le 16$ ），最佳配置通常通过启发式算法（如模拟退火）发现，但缺乏严格的数学证明。特别是对于 $n=9$ ，之前的最佳证明需要数天甚至数月的计算时间（使用 CPU/GPU 集群），且尚未完全确认 Comellas 和 Yebra (2002) 提出的配置是否为全局最优。

2. 方法论 (Methodology)

作者提出了一种**“先优化，后细化” (Optimize-then-Refine)** 的框架，将全局混合整数非线性规划 (MINLP) 与精确符号计算相结合。

2.1 混合整数优化模型 (Mixed-Integer Optimization Model)

作者构建了一个比现有模型更强的 MINLP 模型，主要包含以下创新：

目标函数：最大化最小三角形面积 $z$ 。
绝对值处理：利用辅助变量 $b_t \in \{0, 1\}$ 将非光滑的绝对值约束 $z \le |A_t|$ 转化为双线性约束 $z \le (2b_t - 1)A_t$ ，避免了大 $M$ 法 (Big-M) 带来的松弛松弛问题。
对称性破缺策略 (Symmetry-Breaking)：这是模型性能提升的关键。
- 基于理论证明（命题 3），最优配置中凸包的至少 5 个顶点位于单位正方形的边界上。
- 利用这一性质，强制指定 5 个点位于特定边界（左、下、右、上边及左上角），并按逆时针顺序标记。
- 固定了 5 个点的坐标（如 $x_1=x_5=y_2=0, x_3=y_4=1$ ），并消除了二面体群 $D_4$ 和对称群 $S_n$ 带来的巨大对称性。
- 这极大地减少了搜索空间，使得求解器无需遍历数百万个等价分支。
符号固定：利用边界点的排列顺序，预先确定某些三角形面积的符号（正或负），从而固定部分二进制变量。
变量替换：引入辅助变量 $w_{ij} = x_i y_j$ 以隔离双线性项，便于求解器处理非凸性。

2.2 优化 - 细化框架 (Optimize-then-Refine Framework)

该流程分为两步：

步骤 1：全局计算认证
- 使用 Gurobi 求解器求解上述 MINLP 模型。
- 获得数值解，并验证上下界是否闭合，从而认证全局最优值 $\Delta_n$ 。
- 识别“临界三角形”（面积等于最小值的三角形）和位于边界上的点。
步骤 2：精确符号细化
- 将步骤 1 识别出的结构（哪些点在边界、哪些三角形面积相等）作为假设。
- 建立多项式方程组（令临界三角形面积相等）。
- 使用计算机代数系统（SymPy）求解该方程组，获得精确的代数坐标（通常涉及根式）。
- 通过符号验证确保解的正确性。

3. 主要贡献 (Key Contributions)

更强的混合整数公式：
- 通过基于边界结构的对称性破缺策略，显著提升了模型强度。
- 性能突破：对于 $n=9$ ，在标准桌面计算机上仅需 15 分钟 即可证明全局最优性。相比之下，之前的研究（如 Monji et al., 2025）需要约 1 天，而 Chen et al. (2017) 甚至需要 125 天。效率提升了超过一个数量级。
首次证明 $n=9$ 的全局最优性：
- 结合数值认证和符号计算，首次严格证明了 Comellas 和 Yebra (2002) 发现的 $n=9$ 配置是全局最优的。
- 此前，Monji 等人虽然数值上认证了 $\Delta_9$ 的值，但未将其与 Comellas 的精确解联系起来。
精确坐标的推导：
- 推导出了 $n=5$ 到 $n=9$ 所有最优配置的精确解析坐标（Closed-form exact coordinates）。
- 简化了以往结果的表达形式（例如 $n=7$ 的坐标表达比 Comellas 和 Yebra 的更简洁）。
可复现性与数据公开：
- 收集并整理了 $n \le 16$ 的所有已知最佳配置。
- 公开了完整的源代码、输入数据和结果文件，为后续研究提供了可复现的基础。

4. 关键结果 (Key Results)

作者成功求解并验证了 $n=5$ 至 $n=9$ 的最优解：

$n$	最小面积 $\Delta_n$ (精确值/近似值)	临界三角形数量	备注
5	$\frac{\sqrt{3}}{9} \approx 0.19245$	4	确认已知结果
6	$\frac{1}{8} = 0.125$	6	存在单参数族解
7	$f - \frac{1}{2}$ (其中 $f$ 是 $19f^3-27f^2+11f-1=0 $的根)$ \approx 0.08386$	8	首次提供简洁的精确坐标证明
8	$\frac{\sqrt{13}-1}{36} \approx 0.08386$	12	确认 Dehbi 和 Zeng (2022) 的结果
9	$\frac{9\sqrt{65}-11}{320} \approx 0.08386$	11	首次证明全局最优性，涉及 $\sqrt{65}$

注： $n=9$ 的最优值约为 $0.083859 $，与$ n=7, 8$ 非常接近，显示出该问题的复杂性。

5. 结构观察与新问题 (Structural Observations & New Questions)

通过对认证后的最优配置进行分析，作者发现了两个值得注意的模式：

临界三角形数量的增长：随着 $n$ 增加，临界三角形（面积最小的三角形）的数量总体呈上升趋势（ $n=5$ 时为 4 个， $n=8$ 时为 12 个），但并非严格单调（ $n=9$ 降为 11 个）。这引发了关于临界三角形数量下界的研究问题。
非临界三角形面积的聚类：除了最小面积外，其他三角形的面积并非连续分布，而是聚集在少数几个离散值附近。
- 例如， $n=8$ 时，56 个三角形中，12 个是最小值，其余 44 个明显聚集成几个狭窄的簇。
- 这一现象暗示了极值点集具有超越最小面积优化的深层结构刚性，可能隐藏着未被发现的对称性。

6. 意义与展望 (Significance & Outlook)

方法论意义：该论文展示了混合整数非线性规划 (MINLP) 求解器（如 Gurobi）在处理复杂几何优化问题上的成熟度。通过结合数值优化和符号计算，可以解决过去仅靠数值方法无法处理或无法提供严格证明的问题。
领域影响：为离散几何中的打包和覆盖问题提供了一种通用的解决范式。
未来方向：
- 利用硬件和求解器的进步，尝试将全局认证扩展到 $n=10$ 甚至更高。
- 从理论上解释非临界三角形面积的聚类现象。
- 建立临界三角形数量的非平凡下界。

总结：这篇论文通过创新的对称性破缺策略和“数值 + 符号”的双阶段框架，极大地加速了海因布伦三角形问题的求解过程，首次严格证明了 $n=9$ 的最优性，并揭示了最优配置中深刻的代数结构和几何规律。