Empirical Asymptotic Runtime Analysis of Linear Programming Algorithms

來自最佳化軟體巨頭 Gurobi 的最新實證研究指出，當線性規劃（LP）模型規模持續膨脹時，PDHG（主對偶混合梯度法） 的漸近運行時間增長率最低，但其產生的約束違反誤差卻高達 10^-4，與單純形法（Simplex）的 10^-10 有著巨大的精度落差。這項涵蓋 6 大應用領域、600 個測試實例 的研究，利用大語言模型生成測試集並透過冪次法則迴歸分析，揭示了未來巨型 LP 求解器在「速度與精度」之間無法避免的根本性妥協。

LLM 生成 600 個從 100 秒到 10000 秒求解時間的測試模型

評估演算法的漸近生長率（Asymptotic Runtime Growth）需要特徵相似但規模不同的模型實例。研究團隊採用 ChatGPT 5.4 Thinking 生成了六個領域的合成模型生成器，包含航空機隊指派（Fleet）、天然氣網路（GasNet）、生產計畫（ProdPlan）、供應鏈網路設計（SCND）、電信網路設計（TelecomND）與電力機組排程（UnitCommit）。這六大領域在實務上皆高度依賴大型且困難的線性規劃求解。

設定實例規模時，團隊藉由線性插值調整輸入參數，為每個模型家族生成 100 個實例。最小的實例約可在 100 秒內求解，最大的實例則需要兩種以上演算法耗費 10,000 秒才能完成。透過捕捉約束矩陣中的非零元素（Non-zeros）數量作為模型規模指標，團隊建立了一組既具備現實商業特徵、又能精確對齊漸近分析需求的巨型測試基準。

套用冪次法則（Power-law，即運行時間 = a × 規模^b）進行對數線性迴歸後，研究發現約束矩陣的非零元素數量，幾乎完美符合模型行列數的多項式函數，為後續預測演算法效能打下了堅實的數學基礎。

Simplex、內點法與 PDHG 的 10^-10 至 10^-4 精度層級差異

探討運行時間前，必須先理解三種主流線性規劃演算法的結構與精度特性。單純形法（Simplex） 隨時維護一個基礎解（Basis），具備極高的精確度（平均絕對約束違反誤差約 10^-10）與熱啟動優勢，但其每次迭代皆須求解稀疏線性系統且高度依賴前次結果，難以利用現代多核心架構進行平行化。

部署於多核心環境的 內點法（Interior-Point Method, IPM） 則依賴稀疏 Cholesky 分解來尋找改善方向，具備局部二次收斂特性。其最終精確度落在 10^-8 左右，但運算過程必須依賴減少填充排序（Fill-reducing ordering）來降低矩陣分解成本，且產出的內部解通常需要額外步驟才能轉換為基礎解。

崛起於 2020 年代的 PDHG 演算法，運算主要由稀疏矩陣向量乘法與純量操作構成，完美契合現代 GPU 的極端平行架構。然而，身為一階方法的 PDHG 收斂速度緩慢，商業實作通常在誤差達 10^-6 甚至 10^-4 時即終止計算。這意味著 PDHG 雖然單次迭代成本極低，卻在根本上犧牲了數個數量級的精確度。

冪次法則迴歸顯示 PDHG 漸近時間增長率最低且 R平方大於 0.74

執行單純迭代運算的迴歸測試時（不含預處理與後續轉換），模型顯示出極高的預測能力。在純 CPU 環境（AMD EPYC 4364P）下，內點法的決定係數（R²，即模型解釋變異的比例）在所有測試集中皆大於 0.92，對偶單純形法（Dual Simplex）大於 0.81，PDHG 除了在 GasNet 測試集外，R² 皆大於 0.74。

分析預測指數（冪次法則中的 b 值）發現，PDHG 在除了 UnitCommit 之外的所有測試集中，具備最小的漸近時間增長率；相對地，對偶單純形法的指數則在多數情況下居冠。這證實了當約束矩陣無止盡擴大時，PDHG 的核心迭代時間膨脹得最慢，展現了面對未來巨型模型的潛力。

檢視唯一的例外 GasNet 測試集，PDHG 展現了極不穩定的運算時間，即使嘗試將資料套用多項式、指數或對數函數，依然無法改善預測品質。團隊指出，演算法的迭代次數經常受到矩陣條件數（Condition Number）等數值特性的干擾，導致特定拓樸結構在第一階方法下產生難以預測的震盪。

交叉過渡算法的成本增長率超越 IPM 與 PDHG 主迭代

完整的線性規劃求解並非只有主迭代，還包含預處理（Presolve）與交叉過渡（Crossover，將內部解或近似解轉換為精確基礎解的演算法）。研究數據顯示，預處理的時間增長幾乎與矩陣非零元素數量呈線性關係，代表隨著模型變大，預處理佔用的總時間比例將不斷微縮。

敲響效能警鐘的是交叉過渡算法。迴歸數據表明，對於 IPM 和 PDHG 而言，Crossover 的時間增長預測指數經常大於主迭代的指數。由於交叉過渡算法在本質上與單純形法類似，同樣具備強烈的序列計算限制，這暗示著在極大規模的模型下，取得基礎解的成本將反客為主，主導整體的求解時間。

遭遇低精度初始解時，這個問題會被急遽放大。在 PDHG 的測試中，由於其拋出的近似解誤差較大，不僅 Crossover 的耗時增長率全面高於 PDHG 主迭代，在 Fleet 與 GasNet 測試集中，PDHG 甚至無法在 50,000 秒的時限內順利找到足夠數量的基礎解，導致資料嚴重缺失。

現代 CPU 與 GPU 實測下的絕對效能與求解器選擇權衡

為驗證絕對效能，團隊改用 64 核心的 AMD EPYC 9575F 處理器搭配擁有 96 GB 記憶體的 Nvidia RTX Pro 6000 GPU 進行頂尖對決。如果不執行交叉過渡（容忍低精度），GPU 驅動的 PDHG 在 GasNet 與 ProdPlan 上擊敗了 IPM，而 IPM 則在 Fleet 上勝出，其餘三組則平分秋色。

一旦強制開啟交叉過渡以追求相等的精確度，戰局立刻逆轉。在兩者皆能產出基礎解的五個測試集中，IPM 在 Fleet 與 SCND 上顯著快於 PDHG，在 TelecomND 與 UnitCommit 上兩者相近，PDHG 僅在 ProdPlan 上保有優勢。測量時間佔比更顯示，PDHG 花在交叉過渡的比例普遍遠高於 IPM。

檢視所有數據，LP 演算法的發展正走向嚴格的物理學式權衡。PDHG 具備最低的漸近時間增長率與最佳的硬體擴展性，但犧牲了精度；Simplex 與 Crossover 能提供完美的數值穩定度與基礎解，卻受困於序列計算的本質。若無法開發出全新的平行化交叉算法，強迫高平行度演算法產出高精確解，將失去其時間複雜度上的所有紅利。

面對持續膨脹的最佳化模型，單純追求高度平行化的 PDHG 雖能壓低漸近運算時間，但極其昂貴的基礎解轉換成本，將迫使業界在未來重新定義運算精度標準。