GLPK/故障排除

此頁面討論使用 GLPK 時偶爾會遇到的問題。並且，在可能的情況下，提供典型的 GLPK 警告訊息以幫助診斷。

混合整數問題的連續解

您成功地使用對glp_intopt的呼叫解決了您的 MIP 問題，然後發現最佳解決方案不是預期中的整數值。

檢查您是否使用正確的例程查詢資訊。您應該使用glp_mip_col_val, glp_mip_row_val，以及glp_mip_obj_val來恢復 MIP 解決方案。相反，例程glp_get_col_prim和glp_get_row_prim返回 LP 鬆弛的解決方案。

MPS 格式和 OBJSENSE

看起來很奇怪，MPS 線性程式問題格式的規範不包含目標方向的說明符。也沒有標準的預設值 - 無論是最小化還是最大化。但 GLPK 假設目標是 MPS 檔案中的最小化。一些求解器接受非標準的OBJSENSE說明符作為對 MPS 規範的擴充套件，但 GLPK 會靜默地忽略此關鍵字。

如果使用 GLPSOL，可以透過命令列設定目標方向--min或--max。嚴格來說，使用--min是多餘的。如果您不想使用--max，則可以將目標函式係數乘以 -1。解決方案將被正確報告，但目標值將保留錯誤的符號。

如果您的目標值為零，而您期望的是其他值，那麼您可能無意中部署了錯誤的目標方向。

匯出時忽略目標偏移項

目標函式中的常數項在 GLPK 中被稱為“偏移”項。如果您在 GLPK 下執行模型，此項將被考慮在內。但如果您將模型匯出到 CPLEX LP 和 MPS 格式，則此項不會被傳輸。這將導致變數值正確，但目標值將與“偏移”項不同。

在以下模型中，目標的常數項為 5。

var x, >=0; 
minimize obj : x + 5;

此檔案可以使用以下命令匯出到 CPLEX 格式

glpsol -m test.mod --wlp test.lp --check

控制檯輸出包含一個警告

glp_mpl_build_prob: row obj; constant term 5 ignored

匯出的檔案包含一個帶有常數項的註釋。

\* Problem: test *\

Minimize
 obj: + x
\* constant term = 5 *\

Subject To

End

為了規避這個問題，可以引入一個額外的變數和約束 [1]。

var x, >=0; 
var v_dummy;
s.t. c_dummy : v_dummy = x + 5;
minimize obj : v_dummy;

記憶體不足

對於某些最佳化問題，記憶體，而不是處理能力，可能是系統約束。如果 GLPK 無法透過作業系統獲得對 RAM 記憶體的請求，它應該報告（然後失敗）

umalloc: size = 166550392; no memory available

此訊息意味著 GLPK 例程嘗試從系統中獲得一個 166.6 Mb 的記憶體塊，但嘗試失敗 - 也就是說，對malloc的系統呼叫返回NULL。這意味著您的問題沒有足夠的 RAM（或者記憶體正在從某個程序洩漏，但不太可能是從 GLPK 洩漏）。

此外，如果 GLPK 由於記憶體不足而異常終止，它始終會向標準輸出列印一條訊息。如果未顯示任何訊息，則異常終止不是由 GLPK 引起的（儘管存在 GLPK 錯誤）。

以下執行緒討論了 GLPK 對記憶體的使用，可能為一些記憶體消耗計算提供一個有用的起點。

一些背景

該glp_prob問題物件，在 API 級別，需要額外的記憶體來儲存各種 GLPK 例程使用的輔助資訊。例如，儲存在object中的一個約束矩陣元素（型別為glp_probdoubleglp_prob）需要 32 位元組（在 32 位平臺上），而不是 8 位元組。因此，儲存在

object

使用 GLPSOL 拆分作業

[編輯 | 編輯原始碼]為了減少使用 GLPSOL 時的記憶體需求，您可以拆分作業，如下所示:

glpsol --model foo.mod --data foo.dat --check --wglp foo.glp

翻譯模型並將其寫入foo.glp:

glpsol --glp foo.glp --write foo.sol

解決已翻譯的模型，並將它的解寫入

glpsol --model foo.mod --data foo.dat --read foo.sol

foo.sol使用先前找到的解決方案處理模型另請注意，資料檔案foo.dat和使用先前找到的解決方案處理模型是可選的，而

foo.mod

使用 API 明智地使用記憶體[編輯 | 編輯原始碼], LP 問題通常使用稀疏矩陣構建。最常用的問題構建 API 呼叫是，以及glp_set_mat_rowglp_set_mat_col

glp_load_matrix
。為了最小化記憶體消耗

只複製非零值

ind = GLPK.new_intArray(3);
GLPK.intArray_setitem(ind, 1, 1);
GLPK.intArray_setitem(ind, 2, 2);
val = GLPK.new_doubleArray(3);
GLPK.doubleArray_setitem(val, 1, 1.);
GLPK.doubleArray_setitem(val, 2, -1.);
GLPK.glp_set_mat_row(lp, 1, 2, ind, val);
GLPK.delete_doubleArray(val);
GLPK.delete_intArray(ind);

在使用後刪除臨時陣列和向量

當然，另一種策略是增加系統記憶體。新增 DRAM 顯然是最佳選擇。另一種選擇是檢查您的交換分割槽並將其增加到 DRAM 容量的 8 倍，或遷移到固態硬碟。

數值不穩定性

一位使用者報告說，在使用 GLPK API 求解數百萬個微小的自動生成的 LP 時，偶爾會遇到以下控制檯訊息

Warning: numerical instability (primal simplex, phase II)

這意味著單純形求解器檢測到當前基本解由於過大的舍入誤差而變得不可行。在這種情況下，求解器會自動切換到階段 I 以恢復可行性，然後繼續搜尋。如果求解器例程返回 0，則可以認為該解在當前工作精度內是準確的。GLPK 例程lpx_check_kkt隨後可用於檢查解是否滿足可行性和最優性的各種條件，如此處和此處所述。有關更多資訊，請參見此執行緒。

從 GLPK 4.46 開始，計劃採用更穩健的策略來處理數值不穩定性。此新版本將意味著這些不穩定性警告將不再出現。有關一些詳細資訊，請參見 2011 年 4 月的此帖子。

內點求解器

使用者應注意，內點求解器在求解牛頓系統時，有時會由於數值不穩定性而過早地終止其對解的搜尋。在這種情況下，應使用更穩健的單純形求解器。此 2011 年的帖子包含更多詳細資訊。

緩慢的模型

有時，建模者會建立一個難以解決的問題。對於純（IP）和混合整數（MIP）模型，這種情況比嚴格的線性（LP）模型更常見。另一方面，GLPK 使用的分支定界方法可以以不同的方式執行，切換到另一種變體可能會成功。

大多數這些變體可以透過 GLPSOL 使用其 **命令列選項** 進行訪問。API 自然提供了更大的靈活性。例如，從預設的 GLPSOL 選項切換到--gomory—pcost對於一個玻璃製造模型，它在 2 分鐘內產生了解，而對於另一個原本很慢的模型，它卻很痛苦。

或者，模型可以 **重新表述** 以提高其易處理性或減小其大小。

最後一個選項是嘗試 **另一個求解器**。您的問題類別可能更適合專門的求解器。最後，眾所周知，高調的商業求解器比其免費軟體對應產品更快、更健壯。

約束程式設計問題

MIP 求解器通常在約束程式設計問題上表現不佳。GLPK 也不例外。

如果您的例項是純 0-1 且約束係數是整數，請嘗試使用 **MiniSat** 求解器。此專業求解器受 GLPSOL 支援，也可以透過 GLPK API 獲得。MiniSat 本身在此處有介紹。

呼叫--minisat選項（如果使用 GLPSOL），在這種情況下，GLPK 會將您的例項轉換為可滿足性問題，並使用minisat求解器進行求解。詳細資訊在 GLPK 參考手冊中給出。示例模型（“按數字繪畫”拼圖）可以在以下子目錄中找到：glpk/examples/pbn。您可以使用--objbnd選項除了識別更好的整數可行解。此選項上的bound引數在目標函式上引入了額外的不等式約束。檢查--help訊息以獲取使用詳細資訊。

一位使用者報告說，一個傳統上需要 15 小時才能解決的問題，使用 MiniSat 求解器“幾乎可以立即”解決。

超執行緒硬體

有點矛盾的是，強大的多核超執行緒硬體可能會導致 GLPK 的效能下降。可以透過更改您的 BIOS 設定來停用超執行緒。事實上，這可能會使您的速度提高一倍。有關更多資訊，請參見 2013 年初的此帖子。

解排序

如果您需要快速列出行和列，並按 GLPSOL 處理它們的順序進行排列，請使用以下命令

glpsol --output quick.out --tmlim 1

系統時間同步錯誤

在 4.47 版本之前，每當系統時鐘被讀取兩次且新讀取的時間戳小於先前讀取的時間戳時，GLPK 斷言就會失敗——這種情況會在 GLPK 執行期間作業系統與 NTP 伺服器同步時發生。有關原始錯誤報告，請參見此處，有關該主題的一些更多流量，請參見此處。此錯誤現在從 4.47 版本開始修復。

資料庫和電子表格問題

請參見 ODBC 頁面。

編譯時問題

一些故障排除提示在此處給出。

預編譯二進位制檔案

確保在 64 位系統上使用 64 位二進位制檔案，在 32 位系統上使用 32 位二進位制檔案。這似乎更多是 Windows 使用者的問題。