大模型時(shí)代重訪組合幾何問(wèn)題全局優(yōu)化

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

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

摘要

由DeepMind的AlphaEvolve所代表的大語(yǔ)言模型驅(qū)動(dòng)算法發(fā)現(xiàn)的最新進(jìn)展，已為一系列困難的幾何與組合問(wèn)題產(chǎn)生了新的已知最優(yōu)解。這自然引出一個(gè)問(wèn)題：當(dāng)這些問(wèn)題被直接表述為非線性優(yōu)化問(wèn)題（NLP）時(shí)，現(xiàn)代現(xiàn)成的全局優(yōu)化求解器能在多大程度上匹配此類結(jié)果？

我們重新審視了AlphaEvolve基準(zhǔn)測(cè)試套件中的部分問(wèn)題，并使用兩款最先進(jìn)的求解器——商業(yè)軟件FICO Xpress和開(kāi)源軟件SCIP——對(duì)直接的NLP表述進(jìn)行評(píng)估。在未對(duì)求解器作任何修改的情況下，兩款求解器均復(fù)現(xiàn)了文獻(xiàn)中先前報(bào)告的最佳解，并在若干情形下優(yōu)于這些解，包括近期由大語(yǔ)言模型驅(qū)動(dòng)所發(fā)現(xiàn)的結(jié)果。

我們的結(jié)果不僅凸顯了通用NLP技術(shù)的成熟度及其解決十年前尚超出通用求解器能力范圍的非線性數(shù)學(xué)問(wèn)題的能力，同時(shí)也將全局NLP求解器定位為可在大語(yǔ)言模型驅(qū)動(dòng)算法發(fā)現(xiàn)中加以利用的強(qiáng)大工具。

關(guān)鍵詞：非線性優(yōu)化 · 圓堆積 · 六邊形堆積 · 距離比

1 引言
過(guò)去十年間，全局優(yōu)化技術(shù)的飛速發(fā)展極大地拓展了可求解至證明全局最優(yōu)解（或至少獲得具有可靠對(duì)偶界的高質(zhì)量解）的非線性、非凸問(wèn)題的范圍。以SCIP [20]為代表的先進(jìn)學(xué)術(shù)求解器與FICO? Xpress [3]等商業(yè)求解器，融合了空間分支定界、自動(dòng)線性化與凸化、復(fù)雜的預(yù)處理技術(shù)以及日益強(qiáng)大的原始啟發(fā)式算法 [4,5,6]，使其能夠求解若干年前仍被視為計(jì)算上難以處理的問(wèn)題實(shí)例。

與此同時(shí)，基于大語(yǔ)言模型（LLMs）的算法設(shè)計(jì)新進(jìn)展，重新引起了人們對(duì)一系列可表述為非線性優(yōu)化模型的長(zhǎng)期存在的幾何與組合問(wèn)題的關(guān)注。具體而言，DeepMind 提出了 AlphaEvolve 框架 [19,25]，該框架在進(jìn)化搜索中使用大語(yǔ)言模型生成的代碼，為大量數(shù)學(xué)問(wèn)題（包括圓堆積、六邊形堆積及點(diǎn)集最小距離構(gòu)型的多種變體）生成了高質(zhì)量解。這些突破性成果自然引出一個(gè)問(wèn)題：在具有挑戰(zhàn)性的非線性問(wèn)題上，最先進(jìn)的全局優(yōu)化求解器在多大程度上能夠匹配甚至超越此類自動(dòng)生成的算法？

更廣泛地看，過(guò)去幾年中，將生成模型與結(jié)構(gòu)化搜索及自動(dòng)化評(píng)估或驗(yàn)證相結(jié)合的大語(yǔ)言模型驅(qū)動(dòng)發(fā)現(xiàn)工作流取得了快速進(jìn)展。FunSearch 將大語(yǔ)言模型與進(jìn)化式程序搜索及任務(wù)特定評(píng)估器相結(jié)合，從而在若干離散數(shù)學(xué)與算法問(wèn)題上實(shí)現(xiàn)了改進(jìn) [28]。相關(guān)進(jìn)展還包括 AlphaDev，它利用基于學(xué)習(xí)的搜索重新發(fā)現(xiàn)并改進(jìn)了排序例程等底層算法 [24]；以及 AlphaGeometry，它將神經(jīng)生成與符號(hào)推理相結(jié)合，在無(wú)需人類演示的情況下求解奧林匹克級(jí)別的幾何問(wèn)題 [33]。類似的大語(yǔ)言模型加進(jìn)化方法亦被用于設(shè)計(jì)組合優(yōu)化的有效啟發(fā)式算法 [23]。這些進(jìn)展共同促使我們以經(jīng)典數(shù)學(xué)優(yōu)化方法作為競(jìng)爭(zhēng)性且可靠的基線，重新審視相同的挑戰(zhàn)性基準(zhǔn)問(wèn)題。

在本工作中，我們重新審視了 AlphaEvolve 基準(zhǔn)測(cè)試套件中的三個(gè)問(wèn)題，并通過(guò)非線性規(guī)劃（NLP）的視角對(duì)其進(jìn)行研究。非線性規(guī)劃是一類優(yōu)化問(wèn)題，其目標(biāo)是在由連續(xù)變量上的非線性約束所定義的可行集上，最小化一個(gè)非線性目標(biāo)函數(shù)：

除了呈現(xiàn)有效的工作模型并確定一些驅(qū)動(dòng)性能的關(guān)鍵建模決策外，我們的主要貢獻(xiàn)如下：

使用未修改的求解器獲得更強(qiáng)的解。借助現(xiàn)成的 Xpress 和 SCIP，我們獲得了解與先前報(bào)告的最佳已知結(jié)果一致，并且在多個(gè)案例中有所改進(jìn)的解。某些問(wèn)題僅使用一個(gè)求解器解決，有些問(wèn)題則同時(shí)使用了兩個(gè)求解器。在本文中，我們不區(qū)分是哪個(gè)求解器找到了哪個(gè)解。我們求解器產(chǎn)生的所有解均使用 AlphaEvolve 倉(cāng)庫(kù)中的驗(yàn)證代碼進(jìn)行了驗(yàn)證。

學(xué)到的經(jīng)驗(yàn)。我們反思了基于大語(yǔ)言模型（LLM）方法與非線性優(yōu)化各自的優(yōu)缺點(diǎn)，討論了建模見(jiàn)解，以及全局優(yōu)化軟件如何已成為應(yīng)對(duì)挑戰(zhàn)性組合問(wèn)題的互補(bǔ)且行業(yè)就緒的工具。

這些見(jiàn)解在第 5 節(jié)中討論，而第 2–4 節(jié)各呈現(xiàn)一個(gè)模型，并附帶相應(yīng)的計(jì)算結(jié)果。由于篇幅限制，我們不會(huì)討論對(duì)偶界及其可能的改進(jìn)方法（如更強(qiáng)的表述或?qū)ΨQ性破除），盡管這是啟發(fā)式方法與通用優(yōu)化求解器之間的關(guān)鍵區(qū)別點(diǎn)。

2 最小化最大與最小距離之比

在有限點(diǎn)集中最小化最大與最小成對(duì)距離之比的問(wèn)題，稱為最小-最大比率問(wèn)題（min-max ratio problem），其起源可追溯至經(jīng)典極值幾何學(xué)。Bateman 與 Erd?s [2] 從如下角度提出了該問(wèn)題：對(duì)于給定數(shù)量的點(diǎn)，確定平面上滿足任意兩點(diǎn)間距離至少為 1 的點(diǎn)構(gòu)型，使得點(diǎn)集的直徑最小化。當(dāng)將最小距離歸一化為 1 時(shí)，該問(wèn)題等價(jià)于最小化最大距離與最小距離的比值。Bateman 與 Erd?s 給出了二維情形下 n ≤ 7 的最優(yōu)解。David Cantrell（參見(jiàn)，例如 [16]）在二維和三維情形下貢獻(xiàn)了眾多已知最優(yōu)解；而 Audet 等人則明確將該問(wèn)題表述為非線性優(yōu)化模型，并利用無(wú)導(dǎo)數(shù)優(yōu)化技術(shù)為 n ≤ 30 的情形找到了若干改進(jìn)的構(gòu)型 [1]。

2.1 優(yōu)化模型

兩種模型均產(chǎn)生非凸二次約束優(yōu)化問(wèn)題（QCPs），可被現(xiàn)代全局優(yōu)化求解器高效求解。在實(shí)驗(yàn)中，第一種模型表現(xiàn)略優(yōu)，但差異并不顯著。

數(shù)學(xué)建模方法的強(qiáng)大之處在于：我們可用同一模型處理任意維度的點(diǎn)構(gòu)型。關(guān)鍵的是，這可能是優(yōu)化求解器在此問(wèn)題上表現(xiàn)優(yōu)異的原因之一——該模型本質(zhì)上是無(wú)約束的（至少在原始形式下）：任何有限點(diǎn)集必然存在最大和最小成對(duì)距離，因此其比值定義明確。點(diǎn)集無(wú)需滿足額外約束（例如包含在有界區(qū)域內(nèi)），所有約束僅通過(guò)目標(biāo)函數(shù)的輔助變量引入。

2.2 計(jì)算結(jié)果

我們?cè)?Mosel 建模語(yǔ)言 [14] 中實(shí)現(xiàn)了上述模型。所得問(wèn)題實(shí)例的規(guī)模從 7 個(gè)變量和 10 個(gè)約束（二維空間中的三個(gè)點(diǎn)）到 91 個(gè)變量和 876 個(gè)約束（三維空間中的 30 個(gè)點(diǎn)）不等。表 1 中報(bào)告的改進(jìn)解（向上舍入至五位小數(shù)）均通過(guò)該方法獲得，二維情形下的相應(yīng)構(gòu)型如圖 1 所示。對(duì)于許多其他實(shí)例，該方法復(fù)現(xiàn)了當(dāng)前已知的最佳解。

3 在正方形或矩形內(nèi)堆積圓

在多邊形區(qū)域內(nèi)堆積圓的研究可追溯至近 200 年前 [9]。最受關(guān)注的變體之一涉及將固定數(shù)量的單位圓堆積到盡可能小的正方形中；Peikert [26] 對(duì)此提供了良好的綜述。對(duì)于最多二十個(gè)圓的大多數(shù)情形，借助基于多項(xiàng)式系統(tǒng)與 Gr?bner 基計(jì)算的代數(shù)幾何技術(shù)，目前已知其精確最優(yōu)堆積方案，參見(jiàn)，例如 [11]。

在本工作中，我們研究了一種更難證明最優(yōu)性的變體：圓的位置與半徑均為決策變量。具體而言，我們考慮將可變半徑的圓堆積到單位正方形內(nèi)，或在一種輕微松弛下堆積到周長(zhǎng)為 4 的矩形內(nèi)，同時(shí)最大化各圓半徑之和。已知最優(yōu)解主要?dú)w功于 Cantrell [17]，但除了一些平凡情形外，目前尚無(wú)最優(yōu)性證明。

3.1 優(yōu)化模型

給定正整數(shù) n n，我們考慮將 n n 個(gè)圓裝入一個(gè)矩形的問(wèn)題，目標(biāo)是最大化所有圓半徑之和。我們研究?jī)煞N變體：將圓裝入周長(zhǎng)為 4 的任意矩形，以及將圓裝入單位正方形（其周長(zhǎng)也為 4）的特殊情況。數(shù)學(xué)優(yōu)化方法的關(guān)鍵優(yōu)勢(shì)在于，優(yōu)化模型可輕松調(diào)整。這使得我們能夠通過(guò)簡(jiǎn)單添加或修改約束條件來(lái)探索相關(guān)問(wèn)題，例如下文展示的兩種問(wèn)題變體。

此外，該模型僅包含線性與非凸二次約束。

3.2 計(jì)算結(jié)果

首先，我們聚焦于受限問(wèn)題：將圓裝入正方形。通過(guò)兩種求解器均找到了以下改進(jìn)解（向下舍入至五位小數(shù)）（見(jiàn)表2），該解的可視化結(jié)果如圖2所示。

現(xiàn)在轉(zhuǎn)向稍作松弛的版本：將目標(biāo)替換為裝入周長(zhǎng)為4的矩形。顯然，先前所有解在此松弛問(wèn)題中仍可行，但能獲得略優(yōu)解。

4 在正六邊形內(nèi)堆積單位正六邊形

以最優(yōu)方式將各種形狀堆積到其他形狀內(nèi)的問(wèn)題擁有豐富的文獻(xiàn)，從經(jīng)典幾何問(wèn)題與智力謎題 [8,15]，到為設(shè)計(jì)包裝及將箱子裝入貨運(yùn)集裝箱而求解的堆積問(wèn)題 [10,35]。一般而言，待堆積形狀越復(fù)雜，問(wèn)題在理論分析與實(shí)際求解上均愈發(fā)困難。單位圓堆積問(wèn)題已有深入研究（參見(jiàn)第3節(jié)），但更復(fù)雜的形狀通常僅能借助特設(shè)性啟發(fā)式方法處理。

本節(jié)考慮如下問(wèn)題：將 n n 個(gè)邊長(zhǎng)為 1 的正六邊形堆積到邊長(zhǎng)為 R R 的最小正六邊形容器內(nèi)。每個(gè)內(nèi)部六邊形可自由平移與旋轉(zhuǎn)。由于六邊形具有非圓形幾何結(jié)構(gòu)且可旋轉(zhuǎn)，該問(wèn)題顯著復(fù)雜于圓堆積問(wèn)題。然而，它屬于多邊形堆積問(wèn)題的一個(gè)特例——該問(wèn)題要求將由任意閉合非相交線段序列所界定的二維幾何對(duì)象以某種高效方式堆積到容器中。

Jones 等人 [22] 針對(duì)固定尺寸容器的多邊形堆積問(wèn)題開(kāi)發(fā)了優(yōu)化模型，后由 [32] 推廣至凸對(duì)象，并進(jìn)一步由 [27] 擴(kuò)展至非凸對(duì)象。這些方法針對(duì)特定幾何形狀構(gòu)造所謂的擬 φ 函數(shù)（quasi-phi-functions），以表述對(duì)象之間的成對(duì)不重疊條件。下文的六邊形堆積模型以簡(jiǎn)化方式采用該思路，通過(guò)在成對(duì)六邊形交集上定義 Farkas 乘子（參見(jiàn)，例如 [7]）來(lái)排除內(nèi)部重疊。

4.1 優(yōu)化模型

約束條件（25）將旋轉(zhuǎn)角度限制在 [ 0 , ? ]
范圍內(nèi)，這是由于正六邊形的六重旋轉(zhuǎn)對(duì)稱性（超出 ? 的旋轉(zhuǎn)等價(jià)于該范圍內(nèi)的旋轉(zhuǎn)）。最后，外六邊形邊長(zhǎng) R 的下界（27）由初等幾何推導(dǎo)得出：外六邊形面積必須至少等于 n n個(gè)單位六邊形的總面積。

由于三角函數(shù)的存在，這些問(wèn)題具有非凸非線性特性。更復(fù)雜的是，當(dāng)前表述中還包含非線性等式約束，這對(duì)任何求解方法都構(gòu)成挑戰(zhàn)（因?yàn)榈仁郊s束天然更難滿足）。全局求解器通過(guò)多種方式應(yīng)對(duì)這一挑戰(zhàn)（Xpress 和 SCIP 均采用外逼近法）。同時(shí)，更強(qiáng)的約束條件使該問(wèn)題對(duì)特設(shè)啟發(fā)式方法更具挑戰(zhàn)性。這正是我們能夠報(bào)告顯著超越先前最優(yōu)解的領(lǐng)域，表明現(xiàn)代全局求解器在此類強(qiáng)約束問(wèn)題中具有強(qiáng)大優(yōu)勢(shì)——這正是我們多年來(lái)在混合整數(shù)線性優(yōu)化中常見(jiàn)的狀況。

該求解方法可輕松適配于堆積其他正多邊形（三角形、正方形、五邊形等），僅需修改 n n、重新計(jì)算 ρ ρ 與 ? ? 并重新運(yùn)行求解器即可。事實(shí)上，只要已知線性外層表述，任何凸多面體對(duì)象均可通過(guò)結(jié)構(gòu)相似的方式處理，即使在高維空間中亦然，因?yàn)椴恢丿B約束完全依賴于交集可行的 Farkas 乘子定義。這正是數(shù)學(xué)優(yōu)化具有良好泛化能力的一個(gè)例證。

4.2 計(jì)算結(jié)果

以下解由僅使用默認(rèn)設(shè)置的運(yùn)行產(chǎn)生（通常在數(shù)分鐘內(nèi)完成）。對(duì)于最多 10 個(gè)六邊形的情形，求解器成功復(fù)現(xiàn)了已知最優(yōu)解。此后，我們找到了優(yōu)于已知最優(yōu)解的結(jié)果，僅 13 個(gè)六邊形的情形例外——該情形下復(fù)現(xiàn)了已知的平凡解（且極可能為最優(yōu)解），其邊長(zhǎng)為 4。具體而言，我們發(fā)現(xiàn)了以下改進(jìn)解（向上舍入至五位小數(shù)）（見(jiàn)表 3 與圖 3）。

5 結(jié)論

能夠生成代碼的大語(yǔ)言模型為進(jìn)入新問(wèn)題領(lǐng)域提供了有效切入點(diǎn)，并理想情況下可促進(jìn)對(duì)求解方法的技術(shù)無(wú)關(guān)性探索。在本工作背景下，它們亦有助于重新關(guān)注那些仍存在改進(jìn)空間、且已有一段時(shí)間未被數(shù)學(xué)優(yōu)化方法重新審視的經(jīng)典問(wèn)題。我們的結(jié)果表明，現(xiàn)成的全局優(yōu)化軟件可在數(shù)秒至數(shù)分鐘內(nèi)求解困難組合幾何問(wèn)題的直接表述形式。這凸顯了近年來(lái)取得的實(shí)質(zhì)性進(jìn)展，并表明非線性優(yōu)化正逐步接近（混合整數(shù)）線性優(yōu)化在過(guò)去至少二十年中所扮演的角色：一種穩(wěn)健、高效、隨時(shí)可用的黑盒技術(shù)。

與此同時(shí)，數(shù)學(xué)優(yōu)化亦能滿足通常與基于大語(yǔ)言模型方法相關(guān)聯(lián)的若干期望。組合問(wèn)題及其他數(shù)學(xué)問(wèn)題可以非常自然的方式進(jìn)行表述，問(wèn)題定義的變更通常僅需對(duì)模型作微小修改即可快速實(shí)現(xiàn)。隨后可迅速獲得解，其速度可能顯著快于通過(guò)數(shù)十輪大語(yǔ)言模型驅(qū)動(dòng)的代碼生成迭代來(lái)生成、精煉與測(cè)試求解器特定代碼的過(guò)程。

然而，這兩種技術(shù)不應(yīng)被視為相互競(jìng)爭(zhēng)，而應(yīng)視為互補(bǔ)關(guān)系?；诖笳Z(yǔ)言模型的代碼生成所具備的與求解方法無(wú)關(guān)的原型設(shè)計(jì)能力，是探索新問(wèn)題與構(gòu)建新求解思路的有力工具。有趣的是，在一項(xiàng)針對(duì) 26 個(gè)圓堆積問(wèn)題的 OpenEvolve [31] 研究中，大語(yǔ)言模型最終收斂至采用優(yōu)化方法 [30]，即使用 SciPy [29,34] 中實(shí)現(xiàn)的序列最小二乘規(guī)劃表述配合局部求解器。此外，將大語(yǔ)言模型作為優(yōu)化模型編寫(xiě)輔助工具的概念（如 [12,13,21] 所示）亦極具前景。

值得注意的是，在我們的實(shí)驗(yàn)中，相對(duì)無(wú)約束的最小-最大比率問(wèn)題所觀察到的改進(jìn)幅度最小，而約束高度密集的六邊形堆積問(wèn)題則獲得了最大收益。盡管該觀察基于有限的示例集，但它暗示：?jiǎn)栴}約束越強(qiáng)，基于優(yōu)化的方法競(jìng)爭(zhēng)力越強(qiáng)。鑒于現(xiàn)實(shí)工業(yè)問(wèn)題通常以龐大且多樣化的約束集為特征，這些觀察進(jìn)一步支持了全局優(yōu)化已發(fā)展為行業(yè)就緒技術(shù)的觀點(diǎn)。

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