大模型時代重訪組合幾何問題全局優化

大模型時代重訪組合幾何問題全局優化

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