進階 LP 解法

儘管 LP 技術相當成熟度，有些用途仍需要更進階的技巧。例如，我們有許多不同的 LP 演算法和實作項目可用，每個演算法都有強度和弱點。此外，數值不穩定會導致解決工具速度變慢或無法解決特定模型。

本指南將介紹概念，並提供範例，協助您用 LP 解題工具獲得最高效能和可靠性。

概念

本節說明進階使用 LP 解題工具的重要概念。我們假設讀者熟悉 LP 中的重複性概念。

到達網頁演算法系列

下列 LP 演算法可透過 OR-Tools 存取。

  1. Simplex 演算法是第一個實用的 LP 演算法，目前仍然最受歡迎。演算法會沿著可行區域的頂點 (邊角) 行走，反覆提升目標函式的價值，直到達成最佳解決方案為止。Simplex 演算法分為兩種類型：

    1. Primal Simplex 會沿著基本區域可行的頂點採取步驟。這個變體在解決一系列目標函數不同的 LP 問題時，這個變化版本特別能有效解決基本可行區域的問題。
    2. Dual Simplex 會沿著雙可行區域的頂點採取步驟。 這個變體在解決一連串 LP 問題時特別有效，因為這類問題是固定的，例如只有變數的邊界會改變時。因此，在 MIP 解題工具中廣泛使用雙 Simplex。

  2. 障礙或內點方法是 LP 的第二實用演算法系列。阻隔線方法將理論保證有效 (多項式) 融合性與可靠的效能。可在效能不佳時與 Simplex 演算法相輔相成。例如，某些解題工具會同時執行 Simplex 和阻隔線，並先從完成的演算法傳回解決方案。

  3. 第一順位方法是一系列的演算法，只會使用漸層資訊 (即第一順位導數) 引導疊代。梯度下降法是廣為人知的範例這些方法在非線性最佳化和機器學習中很常見。就 LP 而言，第一排序方法可以比 Simplex 和阻隔線來擴充到更大問題，記憶體需求也可能會大幅降低。另一方面，它們對數值問題較敏感，而且可能難以取得高度準確的解決方案。

下表列出「OR-Tools」中提供的 LP 解題工具，並指出每個解題工具中實作的三個演算法系列中有哪些。

解題工具 Simplex 路擋 第一筆訂單
釘鞋 X X
CPLEXL X X
GlopG X
GLPK X X
陀螺儀L X X
PDLPG X
XpressL X X

G 表示解題工具是由 Google 開發。L 表示解除者需要各個第三方開發人員核發的授權。

如需使用哪些解題工具和演算法的建議，請參閱建議。

「解決問題」的真正意涵是什麼？

為了充分利用 LP 解題工具，重要的是，當解題工具聲稱在 LP 問題找到解決方案時，隱含的意義為何。本節將說明回答這個問題所需的基本知識，特別是已知的數值精確度和解決方案的不重複性。

容忍度

LP 解題工具幾乎一律使用浮點算術，因此其解決方案採用數值不精度。為反映這一點，並避免花費已足夠心力的解決方案改善效能，當這些解決方案符合容許條件的條件時，就會接受解決方案，並宣稱已解決問題。

考慮線性程式設計問題

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

及其對應的雙重問題

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

這對問題具有獨特的最佳基本解決方案：$ x_1 = 1, x_2 = 0 $，雙重解決方案 $ y = -2 $。請問解題工具可能接受哪些解決方案最佳化？為回答這個問題，我們定義下列數量：

  • 「雙重性差距」是指基本目標值與雙目標值之間的差異，在本範例中為 $ |(-2x_1 - x_2) - y| $。
  • 基本不可能性是指違反基本限制的項目，在本例中為 $ (\max\{ (x_1+x_2) - 1, 0 \}、\max\{-x_1, 0\}, \max\{-x_2, 0\}) $。
  • 雙功能是指違反雙限制的項目，在本例中為 $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $。

如果雙重性差距、基本不可能性和雙不可能性小於指定的公差，則會將解決方案宣告為最佳1。

值得注意的是，容忍度的應用方式會因求解器和演算法的自然和慣用原因而有所不同。例如，Simplex 演算法中的雙重度只能透過數值精確度來驅動，而即使在確切計算中，原始和雙不可能性也會存在。某些方法會直接強制執行繫結限制 $ x_1 \ge 0、x_2 \ge 0、$ 和 $ y \le 0 $，而其他方法會以不同方式處理繫結限制違反事件 (例如 $x_1 + x_2 \le 1$) 之 $ x_1 \ge 0、x_2 \ge 0、$ 和 $ y \le 0 $，而其他方法的容忍度等於 $x_1 + x_2 \le 1$。在其他求解器中，容忍度和最佳度數是 $felpler，最佳度數的「絕對值」；兩者相較其他是 $felpler，最佳比例參數。

如需容忍度效果的範例，請考慮適用於上述基本雙組的 $ \epsilon = \frac{1}{2} $ 絕對容忍度。解決方案 $ x_1 = 1.5、x_2 = 0、y = -3 $ 的雙重度差距且不可能性均小於或等於 $ \epsilon $，因此解題工具可能會宣告這項解決方案「最佳」。但是，其目標值 (-3) 與真正的最佳目標值 (-2) 不同。$ \epsilon $ 的一般預設值介於 $10^{-6}$ 和 $10^{-8}$ 之間，因此這類極端範例很少見，但並不可行。

解決方案類型

到達網頁問題可能有多個最佳解決方案，在考慮容許容許條件時更是如此。我們會簡單討論上述三種不同 LP 演算法所傳回的解決方案屬性。

Simplex 演算法一律會傳回可用區域的頂點或角落點。在某些情況下，建議採用這些解決方案，因為這類解決方案往往較稀疏。

障礙和第一順位方法通常不會傳回頂點。(理論提供超出本指南範圍的其他特性)。

基於歷史原因，以及頂點解決方案具有吸引人的屬性，因此預設解決方法通常應用跨界連動程序，從障礙演算法找到的解決方案移至最佳頂點。目前，未針對由優先排序方法找到的解決方案提供跨界連動功能。

建議

針對如何進階使用 LP 解題工具，我們提供下列建議。

問題資料資源調度

解決工具可能會因數值問題而導致模型的收斂或失敗速度變慢。造成這類問題的原因有很多，以下提供一個範例。

在 LP 模型中顯示極小或極大數值常數的情況很常見。延續上述範例，如果 \(x_1\) 和 \(x_2\) 代表指派給「供應商 1」或「供應商 2」的比例客戶，且想要充分發揮服務客戶的優勢，我們可能會編寫下列目標函式：

$$ \min -c_1x_1 - c_2x_2 $$

其中：

  • $ c_1 $ 將客戶指派給供應商 1 的好處
  • $ c_2 $ 是為供應商 2 指派客戶的好處

滿足下列限制的雙重可視為可行性，並具有絕對容忍度 $ \epsilon $：

  • $ y \le -c_1 + \epsilon $，
  • $ y \le -c_2 + \epsilon $。

如果 $ c_1 $ 和 $ c_2 $ 的優勢單位是與 $ \epsilon $ 採用相同規模的小小值，則雙可行性條件會變得較弱，因而可能宣告最佳的基本原則。

另一方面，如果福利單位是「微秒」(1 000 000 微美元 = 1 美元)，那麼這個非常大的絕對值在解決方案中會要求取得非常高精確度，但可能會以浮點數的限制非常高。如果以這種方式建構問題，解題工具可能無法收斂。在設計完善問題的過程中，進階模型人員應考量問題的縮放比例是否與解題工具的容忍度一致。

除了避免數值故障之外，容忍度也可以做調整，以便提升效能。Simplex 和阻隔方法不會過於敏感，但若觀察到進度停滯於解決辦法，有時可能會受益於較大的容忍度。另一方面，第一排序方法通常更加敏感。只要情境允許，優先排序方法的使用者即可從較快的解決方案中放鬆身心。

如要瞭解 Glop 的容忍度，請參閱 GlopParameters 中的 primal_feasibility_tolerance、dual_feasibility_tolerance 和 solution_feasibility_tolerance。請注意，演算法會使用 primal_feasibility_tolerance 和 dual_feasibility_tolerance，而 solution_feasibility_tolerance 則需在解開後檢查以標記數值問題。如果是 PDLP，請參閱 eps_optimal_absolute 和 eps_optimal_relative。

如要進一步瞭解這些類型，請參閱 Gurobi 的數字問題指南。雖然這些規範是針對 Gurobi 的使用者編寫，但其中有許多原則通常都適用。

選擇解題工具和演算法

首先，我們會先舉例說明如何選擇解題工具與演算法的影響程度，然後分享選擇 LP 解題工具的指南。

實務上變化

我們針對 Hans Mittelmann 為「基準化」LP 解題工具使用的執行個體，比較這些執行個體的解決時間，藉此呈現不同 LP 演算法和解題工具的效能變化情形。這些執行個體會明確選擇顯示相對效能的極端，因此不一定代表典型行為。

Glop 的基本和雙 Simplex 方法，與 Gurobi 的阻隔方法 (尋找頂點解決方案) 和 PDLP 相比，具有高精確度的高精確度和先進方法。下表報表以秒計算時間，長度上限為 20 分鐘 (1200 秒)。

執行個體 Glop
Primal Simplex		 Glop
Dual Simplex		 Gurobi Barrier
含跨界休旅車		 無十字會的古洛比堡
 PDLP
高精確度		 PDLP
低精確度
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3rd >1200 252.8 144.6 號 3.2 1.1 0.9
savsched1 >1200 >1200 156.0 22.6 號 46.4 32.4
wide15 >1200 20.8 號 >1200 >1200 110 萬 56.3
振奮 178.4 267.5 12.8 12.3 >1200 157.2
S250r10 12.1 520.6 15.2 16.4 >1200 >1200
解題工具版本 OR-工具 9.3 OR-工具 9.3 Gurobi 9.0 Gurobi 9.0 OR-工具 9.3 OR-工具 9.3
solver_specific_parameters (預設值) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

根據這些結果，我們得出的結論如下。

  • 演算法與解題工具的相對效能可能會因單一執行個體的規模順序而異。
  • 沒有任何一個演算法和解題工具，都得與其他的演算法和解題工具一致。
  • 交叉 (預設為啟用) 會增加解決時間，有時甚至會大幅增加。
  • PDLP 有時可以解決低精確度的問題，但準確度有時可能會是高精確度的 10 倍。

如何選擇到達網頁解題工具的簡短指南

由於沒有任何單一 LP 演算法或解題工具最好，建議您採取下列步驟，瞭解如何找出最適合您的用途。請從第一步開始，如果效能不足，請繼續進行下一步驟。

  1. 立即試用 Glop。原因：Glop 是 Google 內部實作的初級和雙 Simplex 方法。Glop 是開放原始碼，可信任 Google 的實際工作環境工作負載。
    • 如果預設設定 (primal Simplex) 成效不佳，請嘗試使用 use_dual_simplex: true 切換為雙 Simplex。
  2. 如果有可用的授權，請嘗試使用商業解析器 (CPLEX、Gurobi 或 Xpress)。嘗試採用 Simplex 和阻隔線的方法。原因：這些解題工具是業界標準且高度最佳化。此外，阻隔方法與 Glop 提供的 Simplex 演算法相輔相成。
    • 如果使用阻隔線，且不需要頂點解決方案，請停用「跨界連動」。
  3. 立即試用 PDLP。調整應用程式的收容度。原因：PDLP 是根據規模最大的問題而設計，其中 Simplex 和阻隔方法會導致記憶體受限，或是速度過慢。如果採用精確但速度較慢的解決方案，PDLP 效能最佳。
  4. 完成所有設定後，您現在已成為進階 LP 使用者！如需進一步協助，請參閱「或」工具支援選項。

  1. 這通常比上述方式更為複雜。求解器通常會在轉換/簡化版本 (稱為 presolved 問題) 上檢查這些條件。在某些情況下，解決問題的解決方案可能遠離解決方案。在這種情況下，這可能會導致 CPLEX 的 OptimalInfeas 或 Glop 的 IMPRECISE 等異常狀態。↩