在過去一個世紀中，從 單純形 到 內部點法（IPM），線性編程（LP）求解器的演進取得了許多重大里程碑式的發展。 原始對偶線性編程（PDLP） 的引入又帶來了另一項重大進展。
NVIDIA cuOpt 現已實施具有 GPU 加速功能的 PDLP。利用先進算法、NVIDIA 硬件、專用 CUDA 功能和 NVIDIA GPU 庫，cuOpt LP 求解器的性能比基于 CPU 的求解器快了 5000 倍以上。
本文將探討 LP 求解器算法的關鍵組件、LP 中的 GPU 加速，以及 Mittelmann 基準測試 和 最小成本流問題 實例上的 cuOpt 性能。
利用尖端創新實現大規模 LPHarnessing cutting-edge innovations for large-scale LP
LP 是一種涉及優化線性目標函數的方法，受一組線性約束。
假設情況：在土地、種子和化肥方面的限制條件下，農民必須決定種植哪些菜以及以何種數量實現利潤最大化。目標是盡快確定最佳收入，同時遵守所有限制條件。
NVIDIA 開發了一個 LLM 智能體示例 ，可幫助對問題進行建模并使用 LP 求解器解決問題。LP 是一種必要的優化工具，在資源分配、生產規劃、供應鏈以及 混合整數編程 (MIP) 求解器的中堅力量中都有應用。在某些情況下，使用數百萬個變量和約束條件在數秒內解決數學問題具有挑戰性，甚至不可能。
在 GPU 上高效解決 LP 問題有三個要求：
- 高效且大規模的并行算法
- NVIDIA GPU 庫和 CUDA 功能
- 先進的 NVIDIA GPU
高效且大規模的并行算法?
Dantzig 于 1947 年推出的 Simplex 仍然是大多數 LP 和 MIP 求解器的核心組件。它的工作原理是遵循可行區域的邊緣來找到最優值。
下一個重大進步是 I. I. Dikin 在 1967 年發現的 內部點法 (IPM)。IPM 通過多面體內部向最佳方向移動，現在被認為是在 CPU 上求解大規模 LP 的先進技術。然而，這兩種技術在大規模并行化方面都面臨局限性。
2021 年，Google 研究團隊推出了解決大型線性規劃（LP）的新突破性技術： PDLP 。這是一種一階方法（FOM），使用問題的導數迭代優化目標并最小化約束違反。
PDLP 通過引入預求解器、對角預處理、自適應重啟和動態原始對偶步長選擇等工具來改進收斂性，從而增強了 原始對偶混合梯度 (PDHG) 算法。預解和預處理使輸入問題更加簡單并提高了數值穩定性，而重啟和動態步長計算則使求解器能夠在優化期間進行自我調整。
與之前的方法相比，FOM 的一個主要優勢是易于大規模并行化，因此非常適合 GPU 實現。
PDLP 采用兩種高度并行的計算模式：Map 操作和稀疏矩陣向量乘法（SpMV）。這種方法使 PDLP 能夠高效地并行處理數百萬個變量和約束，使其在 GPU 上非常有效。
Map 在 PDLP 中廣泛用于對所有變量和約束（可能涉及數百萬個元素）執行加減法等操作。它在 GPU 上非常并行且高效。
SpMV 對應于將稀疏矩陣（包含許多零）與向量相乘。雖然此矩陣的大小可以達到數十億，但其中包含的有用值卻要少得多。例如，在種植蔬菜的問題中，“我不能種植超過 3.5 公斤的馬鈴薯”等約束在數百萬個變量中只包含一個有用值。
SpMV 算法已針對 GPU 進行了廣泛優化，使其比 CPU 實現快幾個數量級。
NVIDIA GPU 庫和 CUDA 功能?
為了獲得最佳性能，我們的 GPU PDLP 實現使用了先進的 CUDA 功能和以下 NVIDIA 庫：
- cuSparse
- Thrust
- RMM
cuSparse 是 NVIDIA GPU 加速的稀疏線性代數庫。它可以高效執行 SpMV，這是 GPU 上一項具有挑戰性的任務。cuSparse 采用獨特的算法，旨在充分利用 NVIDIA 的大規模并行架構。
Thrust 是 NVIDIA CUDA 核心計算庫 (CCCL) 的一部分，提供高級 C++ 并行算法。它使用用于 GPU 執行的模式和迭代器來簡化復雜算法的表達。我使用 Thrust 進行地圖操作和重啟過程，這需要按鍵對值進行排序。這是一項對 GPU 要求較高的任務，但已由 Thrust 進行了高效優化。
RMM 是快速靈活的 NVIDIA 內存管理系統，可通過使用內存池安全高效地處理 GPU 內存。
最后，我利用了先進的 CUDA 功能。在 GPU 上并行化 PDLP 的最大挑戰之一是重啟過程，該過程本質上是迭代的，不適合并行執行。為了解決這個問題，我使用了 CUDA 協作組 ，使您能夠在各個級別定義 GPU 算法，其中最大的是包含所有工作程序的網格。通過實施協作內核啟動和使用網格同步，能夠在 GPU 上高效、優雅地表達迭代重啟過程。
先進的 NVIDIA GPU?
GPUs 通過使用數千個線程并行解決許多問題來實現快速計算。然而，在處理之前，GPU 必須先將數據從主內存傳輸到其工作線程中。
內存帶寬 是指每秒可以傳輸的數據量。CPU 通常可以處理數百 GB/秒，而最新的 GPU NVIDIA HGX B100 的帶寬為 8 GB/秒，高出兩個數量級。
由于嚴重依賴 Map 和 SpMV 等內存密集型計算模式，此 PDLP 實施的性能會直接隨著內存帶寬的增加而擴展。隨著未來 NVIDIA GPU 帶寬的增加，PDLP 將自動變得更快，與其他基于 CPU 的 LP 求解器不同。
cuOpt 在 Mittelmann 基準測試中優于最先進的 CPU LP 求解器
對 LP 求解器的速度進行基準測試的行業標準是 Mittelmann 基準測試 。其目標是在盡可能短的時間內遵循限制條件，確定 LP 函數的最佳值。基準測試問題代表各種場景，包含數十萬到數千萬個值。
為了進行比較，我運行了一臺先進的 CPU LP 求解器，并將其與此 GPU LP 求解器進行了比較。我使用相同的閾值 10^-4，并禁用了交叉。有關更多信息，請參閱本文后面的“ PDLP 精煉潛力 ”部分。
這兩個求解器均在 float64 精度下運行。
- 對于 CPU LP 求解器，我使用了推薦的 CPU 設置：具有 16 個核心和 256 GB DDR4 內存的 AMD EPYC 7313P 服務器。
- 對于 cuOpt LP 求解器，我使用了 NVIDIA H100 SXM Tensor Core GPU，以利用高帶寬，并且在沒有預解析的情況下運行。
我考慮了不使用 I/O 的完整求解時間，包括兩個求解器的擴展和 CPU LP 求解器的預求解。圖 4 僅顯示了為兩個求解器收斂且具有正確目標值的實例。在 60% 的實例中，cuOpt 的速度更快，在 20% 的實例中，速度快 10 倍以上。在一個大型多商品流優化問題的實例中，最大的加速是 5000 倍。
我還在相同的設置和條件下，將 cuOpt 與先進的 CPU PDLP 實現方案進行了比較。cuOpt 的速度持續提高，速度提高了 10 倍到 3000 倍。
多商品流問題（MCF）涉及找到一種最有效的方法，將多種不同類型的商品從不同的起點路由到各自的目的地，確保不超過網絡的容量限制。一種解決 MCF 問題的方法是將其轉換為線性規劃（LP）。在一組大型 MCF 實例中，PDLP 的速度始終保持在 10 倍到 300 倍之間。
PDLP 細化潛力?
NVIDIA cuOpt LP 求解器提供令人驚嘆的性能，但未來仍有可能進行增強：
- 處理更高的準確性
- 需要高帶寬
- 一些收問題
- 小型 LP 權益有限
處理更高的準確性?
要確定您是否已解決 LP 問題，您需要衡量兩件事：
- 最優差距： 測量您距離找到目標函數最優值的程度。
- 可行性： 測量遵守限制條件的程度。
當兩個數量均為 0 時，LP 被視為已解決。達到精確的 0 值可能很具有挑戰性，而且通常沒有必要，因此 LP 求解器使用的閾值可以在保持準確性的同時實現更快的收斂。現在，兩個數量只需低于此閾值，即相對于問題值的大小而言。
大多數 LP 求解器都使用閾值，尤其是對于非常具有挑戰性的大問題。到目前為止，行業標準是使用 10^-8。雖然 PDLP 可以使用 10^-8 來解決問題，但通常速度要慢得多。如果您需要高精度，這可能會成為問題。在實踐中，許多人發現 10^-4 的準確度足夠高，有時甚至更低。這對 PDLP 大有益，同時對于其他 LP 求解算法來說并不是一個很大的區別。
需要高帶寬?
PDLP 的性能隨內存帶寬呈線性擴展，因此在新 GPU 架構上更高效。它需要最近的服務器級 GPU 來重現性能分析部分中顯示的結果。
關于某些問題的收斂問題
雖然 PDLP 可以快速求解大多數 LP，但有時需要大量步驟才能收斂，從而導致更高的運行時間。在 Mittelmann 的基準測試中，由于收斂速度慢，cuOpt LP 求解器在 49 個公共實例中的 8 個實例上超時 1 小時。
小型 LP 權益有限?
與 CPU 求解器相比，GPU 的高帶寬使 Small LPs 無法進行擴展，因此 Small LPs 受益更少。cuOpt LP 求解器為此場景提供了一種批量模式，您可以在其中并行提供并求解數百個 Small LPs。
結束語?
cuOpt LP 求解器使用 CUDA 編程、NVIDIA GPU 庫和最先進的 NVIDIA GPU 來求解 LP，其速度可能比 CPU 快幾個數量級，并可擴展到超過 10 億個系數。因此，它對于解決大規模問題特別有用，因為在這些問題中，其優勢變得更加突出。
在傳統的 Simplex 或 IPM 中，某些用例的效果仍然更好，我希望未來的求解器能夠結合 GPU 和 CPU 技術。
注冊以在 您試用 NVIDIA cuOpt LP 時收到通知。立即通過 NVIDIA 托管的 NIM 微服務試用 NVIDIA cuOpt Vehicle Routing Problem (VRP)，在 NVIDIA API Catalog 上免費獲取最新的 AI 模型。
?
