大模型时代重访组合几何问题全局优化|多边形|新论文|算法|重访组合

大模型时代重访组合几何问题全局优化

Global Optimization for Combinatorial Geometry Problems Revisited in the Era of LLMs

https://www.arxiv.org/pdf/2601.05943

摘要

由DeepMind的AlphaEvolve所代表的大语言模型驱动算法发现的最新进展，已为一系列困难的几何与组合问题产生了新的已知最优解。这自然引出一个问题：当这些问题被直接表述为非线性优化问题（NLP）时，现代现成的全局优化求解器能在多大程度上匹配此类结果？

我们重新审视了AlphaEvolve基准测试套件中的部分问题，并使用两款最先进的求解器——商业软件FICO Xpress和开源软件SCIP——对直接的NLP表述进行评估。在未对求解器作任何修改的情况下，两款求解器均复现了文献中先前报告的最佳解，并在若干情形下优于这些解，包括近期由大语言模型驱动所发现的结果。

我们的结果不仅凸显了通用NLP技术的成熟度及其解决十年前尚超出通用求解器能力范围的非线性数学问题的能力，同时也将全局NLP求解器定位为可在大语言模型驱动算法发现中加以利用的强大工具。

关键词：非线性优化 · 圆堆积 · 六边形堆积 · 距离比

1 引言
过去十年间，全局优化技术的飞速发展极大地拓展了可求解至证明全局最优解（或至少获得具有可靠对偶界的高质量解）的非线性、非凸问题的范围。以SCIP [20]为代表的先进学术求解器与FICO® Xpress [3]等商业求解器，融合了空间分支定界、自动线性化与凸化、复杂的预处理技术以及日益强大的原始启发式算法 [4,5,6]，使其能够求解若干年前仍被视为计算上难以处理的问题实例。

与此同时，基于大语言模型（LLMs）的算法设计新进展，重新引起了人们对一系列可表述为非线性优化模型的长期存在的几何与组合问题的关注。具体而言，DeepMind 提出了 AlphaEvolve 框架 [19,25]，该框架在进化搜索中使用大语言模型生成的代码，为大量数学问题（包括圆堆积、六边形堆积及点集最小距离构型的多种变体）生成了高质量解。这些突破性成果自然引出一个问题：在具有挑战性的非线性问题上，最先进的全局优化求解器在多大程度上能够匹配甚至超越此类自动生成的算法？

更广泛地看，过去几年中，将生成模型与结构化搜索及自动化评估或验证相结合的大语言模型驱动发现工作流取得了快速进展。FunSearch 将大语言模型与进化式程序搜索及任务特定评估器相结合，从而在若干离散数学与算法问题上实现了改进 [28]。相关进展还包括 AlphaDev，它利用基于学习的搜索重新发现并改进了排序例程等底层算法 [24]；以及 AlphaGeometry，它将神经生成与符号推理相结合，在无需人类演示的情况下求解奥林匹克级别的几何问题 [33]。类似的大语言模型加进化方法亦被用于设计组合优化的有效启发式算法 [23]。这些进展共同促使我们以经典数学优化方法作为竞争性且可靠的基线，重新审视相同的挑战性基准问题。

在本工作中，我们重新审视了 AlphaEvolve 基准测试套件中的三个问题，并通过非线性规划（NLP）的视角对其进行研究。非线性规划是一类优化问题，其目标是在由连续变量上的非线性约束所定义的可行集上，最小化一个非线性目标函数：

除了呈现有效的工作模型并确定一些驱动性能的关键建模决策外，我们的主要贡献如下：

使用未修改的求解器获得更强的解。借助现成的 Xpress 和 SCIP，我们获得了解与先前报告的最佳已知结果一致，并且在多个案例中有所改进的解。某些问题仅使用一个求解器解决，有些问题则同时使用了两个求解器。在本文中，我们不区分是哪个求解器找到了哪个解。我们求解器产生的所有解均使用 AlphaEvolve 仓库中的验证代码进行了验证。

学到的经验。我们反思了基于大语言模型（LLM）方法与非线性优化各自的优缺点，讨论了建模见解，以及全局优化软件如何已成为应对挑战性组合问题的互补且行业就绪的工具。

这些见解在第 5 节中讨论，而第 2–4 节各呈现一个模型，并附带相应的计算结果。由于篇幅限制，我们不会讨论对偶界及其可能的改进方法（如更强的表述或对称性破除），尽管这是启发式方法与通用优化求解器之间的关键区别点。

2 最小化最大与最小距离之比

在有限点集中最小化最大与最小成对距离之比的问题，称为最小-最大比率问题（min-max ratio problem），其起源可追溯至经典极值几何学。Bateman 与 Erdős [2] 从如下角度提出了该问题：对于给定数量的点，确定平面上满足任意两点间距离至少为 1 的点构型，使得点集的直径最小化。当将最小距离归一化为 1 时，该问题等价于最小化最大距离与最小距离的比值。Bateman 与 Erdős 给出了二维情形下 n ≤ 7 的最优解。David Cantrell（参见，例如 [16]）在二维和三维情形下贡献了众多已知最优解；而 Audet 等人则明确将该问题表述为非线性优化模型，并利用无导数优化技术为 n ≤ 30 的情形找到了若干改进的构型 [1]。

2.1 优化模型

两种模型均产生非凸二次约束优化问题（QCPs），可被现代全局优化求解器高效求解。在实验中，第一种模型表现略优，但差异并不显著。

数学建模方法的强大之处在于：我们可用同一模型处理任意维度的点构型。关键的是，这可能是优化求解器在此问题上表现优异的原因之一——该模型本质上是无约束的（至少在原始形式下）：任何有限点集必然存在最大和最小成对距离，因此其比值定义明确。点集无需满足额外约束（例如包含在有界区域内），所有约束仅通过目标函数的辅助变量引入。

2.2 计算结果

我们在 Mosel 建模语言 [14] 中实现了上述模型。所得问题实例的规模从 7 个变量和 10 个约束（二维空间中的三个点）到 91 个变量和 876 个约束（三维空间中的 30 个点）不等。表 1 中报告的改进解（向上舍入至五位小数）均通过该方法获得，二维情形下的相应构型如图 1 所示。对于许多其他实例，该方法复现了当前已知的最佳解。

3 在正方形或矩形内堆积圆

在多边形区域内堆积圆的研究可追溯至近 200 年前 [9]。最受关注的变体之一涉及将固定数量的单位圆堆积到尽可能小的正方形中；Peikert [26] 对此提供了良好的综述。对于最多二十个圆的大多数情形，借助基于多项式系统与 Gröbner 基计算的代数几何技术，目前已知其精确最优堆积方案，参见，例如 [11]。

在本工作中，我们研究了一种更难证明最优性的变体：圆的位置与半径均为决策变量。具体而言，我们考虑将可变半径的圆堆积到单位正方形内，或在一种轻微松弛下堆积到周长为 4 的矩形内，同时最大化各圆半径之和。已知最优解主要归功于 Cantrell [17]，但除了一些平凡情形外，目前尚无最优性证明。

3.1 优化模型

给定正整数 n n，我们考虑将 n n 个圆装入一个矩形的问题，目标是最大化所有圆半径之和。我们研究两种变体：将圆装入周长为 4 的任意矩形，以及将圆装入单位正方形（其周长也为 4）的特殊情况。数学优化方法的关键优势在于，优化模型可轻松调整。这使得我们能够通过简单添加或修改约束条件来探索相关问题，例如下文展示的两种问题变体。

此外，该模型仅包含线性与非凸二次约束。

3.2 计算结果

首先，我们聚焦于受限问题：将圆装入正方形。通过两种求解器均找到了以下改进解（向下舍入至五位小数）（见表2），该解的可视化结果如图2所示。

现在转向稍作松弛的版本：将目标替换为装入周长为4的矩形。显然，先前所有解在此松弛问题中仍可行，但能获得略优解。

4 在正六边形内堆积单位正六边形

以最优方式将各种形状堆积到其他形状内的问题拥有丰富的文献，从经典几何问题与智力谜题 [8,15]，到为设计包装及将箱子装入货运集装箱而求解的堆积问题 [10,35]。一般而言，待堆积形状越复杂，问题在理论分析与实际求解上均愈发困难。单位圆堆积问题已有深入研究（参见第3节），但更复杂的形状通常仅能借助特设性启发式方法处理。

本节考虑如下问题：将 n n 个边长为 1 的正六边形堆积到边长为 R R 的最小正六边形容器内。每个内部六边形可自由平移与旋转。由于六边形具有非圆形几何结构且可旋转，该问题显著复杂于圆堆积问题。然而，它属于多边形堆积问题的一个特例——该问题要求将由任意闭合非相交线段序列所界定的二维几何对象以某种高效方式堆积到容器中。

Jones 等人 [22] 针对固定尺寸容器的多边形堆积问题开发了优化模型，后由 [32] 推广至凸对象，并进一步由 [27] 扩展至非凸对象。这些方法针对特定几何形状构造所谓的拟 φ 函数（quasi-phi-functions），以表述对象之间的成对不重叠条件。下文的六边形堆积模型以简化方式采用该思路，通过在成对六边形交集上定义 Farkas 乘子（参见，例如 [7]）来排除内部重叠。

4.1 优化模型

约束条件（25）将旋转角度限制在 [ 0 , ϕ ]
范围内，这是由于正六边形的六重旋转对称性（超出 ϕ 的旋转等价于该范围内的旋转）。最后，外六边形边长 R 的下界（27）由初等几何推导得出：外六边形面积必须至少等于 n n个单位六边形的总面积。

由于三角函数的存在，这些问题具有非凸非线性特性。更复杂的是，当前表述中还包含非线性等式约束，这对任何求解方法都构成挑战（因为等式约束天然更难满足）。全局求解器通过多种方式应对这一挑战（Xpress 和 SCIP 均采用外逼近法）。同时，更强的约束条件使该问题对特设启发式方法更具挑战性。这正是我们能够报告显著超越先前最优解的领域，表明现代全局求解器在此类强约束问题中具有强大优势——这正是我们多年来在混合整数线性优化中常见的状况。

该求解方法可轻松适配于堆积其他正多边形（三角形、正方形、五边形等），仅需修改 n n、重新计算 ρ ρ 与 ϕ ϕ 并重新运行求解器即可。事实上，只要已知线性外层表述，任何凸多面体对象均可通过结构相似的方式处理，即使在高维空间中亦然，因为不重叠约束完全依赖于交集可行的 Farkas 乘子定义。这正是数学优化具有良好泛化能力的一个例证。

4.2 计算结果

以下解由仅使用默认设置的运行产生（通常在数分钟内完成）。对于最多 10 个六边形的情形，求解器成功复现了已知最优解。此后，我们找到了优于已知最优解的结果，仅 13 个六边形的情形例外——该情形下复现了已知的平凡解（且极可能为最优解），其边长为 4。具体而言，我们发现了以下改进解（向上舍入至五位小数）（见表 3 与图 3）。

5 结论

能够生成代码的大语言模型为进入新问题领域提供了有效切入点，并理想情况下可促进对求解方法的技术无关性探索。在本工作背景下，它们亦有助于重新关注那些仍存在改进空间、且已有一段时间未被数学优化方法重新审视的经典问题。我们的结果表明，现成的全局优化软件可在数秒至数分钟内求解困难组合几何问题的直接表述形式。这凸显了近年来取得的实质性进展，并表明非线性优化正逐步接近（混合整数）线性优化在过去至少二十年中所扮演的角色：一种稳健、高效、随时可用的黑盒技术。

与此同时，数学优化亦能满足通常与基于大语言模型方法相关联的若干期望。组合问题及其他数学问题可以非常自然的方式进行表述，问题定义的变更通常仅需对模型作微小修改即可快速实现。随后可迅速获得解，其速度可能显著快于通过数十轮大语言模型驱动的代码生成迭代来生成、精炼与测试求解器特定代码的过程。

然而，这两种技术不应被视为相互竞争，而应视为互补关系。基于大语言模型的代码生成所具备的与求解方法无关的原型设计能力，是探索新问题与构建新求解思路的有力工具。有趣的是，在一项针对 26 个圆堆积问题的 OpenEvolve [31] 研究中，大语言模型最终收敛至采用优化方法 [30]，即使用 SciPy [29,34] 中实现的序列最小二乘规划表述配合局部求解器。此外，将大语言模型作为优化模型编写辅助工具的概念（如 [12,13,21] 所示）亦极具前景。

值得注意的是，在我们的实验中，相对无约束的最小-最大比率问题所观察到的改进幅度最小，而约束高度密集的六边形堆积问题则获得了最大收益。尽管该观察基于有限的示例集，但它暗示：问题约束越强，基于优化的方法竞争力越强。鉴于现实工业问题通常以庞大且多样化的约束集为特征，这些观察进一步支持了全局优化已发展为行业就绪技术的观点。

原文链接：https://www.arxiv.org/pdf/2601.05943