GLPK/Scaling

縮放是指對問題約束矩陣應用線性變換以改善其數值特性的過程。

在 GLPSOL 的情況下，可以使用命令列選項來控制要部署的縮放型別，或者在從程式直接呼叫 GLPK 時透過 GLPK API 來控制。

概述

GLPK 中的縮放由以下函式管理glp_scale_prob. 此頁面上的原始資訊來自該函式及其子函式的原始碼註釋scale_prob, gm_scaling, gm_iterate，和eq_scaling. 關於這一點，GLPK 程式碼庫有很好的註釋，是一個查詢詳細資訊的好地方。

GLPK 中的縮放可能包括以下步驟，以及相應的 按位或運算 縮放選項

• 如果問題已良好縮放，則跳過 GLP_SF_SKIP
• 執行迭代幾何縮放 GLP_SF_GM
• 執行均衡縮放 GLP_SF_EQ
• 將縮放因子舍入到最接近的二的冪 GLP_SF_2N

預設縮放設定GLP_SF_AUTO按順序執行前三個步驟GLP_SF_SKIP, GLP_SF_GM, GLP_SF_EQ. 使用 MIP 預求解器還可以新增GLP_SF_2N.

縮放通常也提供 終端輸出. 更多詳細資訊可以在 官方文件 或直接從原始碼中找到。

檢查問題是否已良好縮放

如果滿足以下條件，則認為問題已良好縮放，

$0.1\leq \left|a_{i,j}\right|\leq 10,\forall a_{i,j}\neq 0$

其中 $a_{i,j}$ 是第 i 行和第 j 列的約束矩陣係數。

迭代幾何縮放

幾何縮放可以平等地應用於行和列。幾何縮放會對每行或每列進行縮放，使得最小值和最大值的絕對值的乘積為 1。

$a'_{i,j}={\frac {a_{i,j}}{\sqrt {\min(\left|a_{i,j}\right|)\times \max(\left|a_{i,j}\right|)}}}$

迭代幾何縮放會交替地對行和列應用幾何縮放，直到達到最大迭代次數或縮放沒有顯著改進。縮放質量 r 由以下公式定義

$r={\frac {\max(\left|a_{i,j}\right|)}{\min(\left|a_{i,j}\right|)}}$

GLPK 預設使用 r 至少 10% 的逐輪改進，並在終止之前進行最多 15 輪。

均衡縮放

均衡縮放可以應用於行和列。均衡縮放會將每行或每列除以該行或列中存在的最大絕對值。

$a'_{i,j}={\frac {a_{i,j}}{\max(\left|a_{i,j}\right|)}}$

均衡縮放使每行和每列的 無窮範數 等於 1。

最接近的二的冪縮放

縮放可能會產生舍入誤差。如果所有縮放因子都是二的冪，則可以避免這些誤差，因為這隻會影響 IEEE 754 表示的雙精度數的指數部分，而不會影響尾數部分。

該演算法首先遍歷所有行，然後遍歷所有列。將每行/列的縮放因子舍入到最接近的二的冪

$f\leftarrow 2^{\lfloor log_{2}({\frac {4}{3}}f)\rfloor }$

重新計算

如果您新增或刪除行或列，或修改現有行/列，則需要呼叫glp_scale_prob再次。在修改的情況下，此呼叫還可能更改一些行和/或列縮放因子，從而更改基矩陣。這將使您在glp_prob物件中儲存的單純形求解器的當前基分解失效，因為分解是針對縮放矩陣而不是原始矩陣計算的。然而，這只是一個效率問題（而不是準確性或穩定性問題），因為如果基分解失效，單純形求解器只會簡單地計算一個新的基矩陣。