GLPK/解決方案資訊

本頁面解釋瞭如何從 GLPK 中恢復和解釋解決方案資訊。此處提供的資訊應與使用 GLPSOL 的建模者和使用可呼叫庫 API 的程式設計師相關。

在使用本頁面的內容之前，您必須嘗試求解您的問題，但 GLPK 的求解過程不一定產生了可用的答案。無論是否有答案，都有很多原因需要尋求有關求解過程和/或解決方案的額外資訊。

執行時報告

GLPK 通常會在求解過程中列印資訊，可以在終端輸出頁面上找到詳細資訊。

無法求解到最優

GLPK 可能無法找到最優解的原因有很多（除了軟體錯誤），

問題為空，求解器返回
求解器證明該問題是無界的，並返回
求解器證明該問題是不可行的，並返回
求解器無法在分配的時間或可用記憶體內找到初始可行解
求解器無法在分配的時間或可用記憶體內找到最優解
求解器遇到數值不穩定問題

並非所有這些情況都與{ 單純形，內點 } × { LP，MIP } 組合中的每一個相關，但這確實給出了可能出現的各種問題的概況。故障排除頁面提供了一些建議和解決方案。特別是數值不穩定警告可能是由於縮放不當導致的。如果您遇到一個非常令人費解的問題，並且認為是 GLPK 中的錯誤，請報告該問題，以便對其進行處理。

如果使用 GLPK 進行程式設計，請記住，求解器可能（也許是矛盾的）不一定找到了解決方案來返回成功 - 它只需要以令人滿意的方式完成其分配的任務。

解決方案恢復

假設 GLPK 提供了最優解，可以使用標準呼叫和定製方法來恢復解決方案資訊，這有幾種方法。某些技術也可以接受和處理非最優可行解。

MathProg 語言允許嚴格控制解決方案資訊的輸出。該語言現在支援針對約束和變數（但不是引數）的字尾 - 這在搜尋例如對偶值時非常有用。關於接近零值的部分展示瞭如何使用 MathProg 條件來輸出真正的零值而不是非常小的數字。

GLPSOL 提供了選項--output和--write分別用於獲得人類可讀和機器可解析格式的解決方案資訊。兩者都可以在一個命令中使用

glpsol ... --output file.out --write file.wri

這兩個輸出格式在互操作性頁面上展示。終端輸出也可以使用 GLPSOL 命令列選項複製到文字檔案--log file.log. 反過來，特殊檔名/dev/stdout可用於將“檔案”寫入終端而不是寫入常規檔案。這兩種策略可以一起使用。

由glp_print_sol產生的輸出類似於 IBM MPS/360 線性規劃軟體包中使用的輸出，但略有修改，因為 GLPK 使用輔助變數而不是鬆弛/盈餘變數。 ^[1]

可以用來恢復資訊的各種 GLPK API 呼叫列在下方。在其他地方，給出了相關的函式名稱，以幫助交叉引用回 GLPK API 手冊，在該手冊中通常可以找到全面的技術描述。

敏感性分析報告

用單純形求解器求解到最優的問題可以進一步進行敏感性分析。此功能不適用於內點求解器生成的解決方案或混合整數問題。該glp_print_rangesAPI 呼叫以人類可讀的格式生成敏感性報告。

GLPSOL 的--ranges選項也生成此報告（或如果其使用不當，則發出適當的警告）

glpsol ... --ranges file.sen

由glp_print_ranges與 IBM MPS/360 線性規劃軟體包中使用的報告相同（參見 Murtagh 1981）。

此處的描述故意簡短 - 詳細資訊可以在官方 GLPK API 手冊中找到，包括對斷點和目標係數敏感性的解釋。以下兩個表格可以用於閱讀敏感性分析報告。

行
標題	值	註釋
`編號`		行的序號， 1 … n
`行名`		符號名稱（如果沒有則為空白）
`St`		行狀態

	`BS`	約束不活動
	`NL`	RHS 較低的非等式約束活動
	`NU`	RHS 較高的非等式約束活動
	`NS`	等式約束活動
	`NF`	自由行活動
`活動`		（主）輔助變數的值
`鬆弛`		（主）鬆弛變數的值
`邊際`		輔助變數的簡化成本（對偶活動）
`下限`		RHS 的下限（`-Inf`如果開啟）
`上限`		RHS 的上限（`+Inf`如果開啟）
`目標係數範圍`		與行相關的目標係數範圍
`目標值`		目標值
`限制變數`		限制變數的名稱

列
標題	值	註釋
`編號`		列的序號， 1 … m
`列名`		符號名稱（如果沒有則為空白）
`St`		列狀態

	`BS`	基本列
	`NL`	下限活動的非基本列
	`NU`	上限活動的非基本列
	`NS`	非基本固定列
	`NF`	非基本自由（無界）列
`活動`		（主）結構變數的值
`目標係數`		結構變數的目標係數
`邊際`		結構變數的簡化成本（對偶活動）
`下限`		結構變數的下限（`-Inf`如果開啟）
`上限`		結構變數的上限（`+Inf`如果開啟）
`目標值`		目標值
`限制變數`		限制變數的名稱

縮寫：RHS 表示右手邊。Inf 表示無窮大。

官方文件（GLPK 4.45）解釋說，對行的分析是對其輔助變數的分析，該變數等於行線性形式 $\sum a_{j}x_{j}$ 。對列的分析是對其對應結構變數的分析。從形式上講，在執行敏感性分析時，行和列之間沒有內在的區別。

Karush-Kuhn-Tucker 最優條件

對於純線性規劃（不包括混合整數規劃），Karush-Kuhn-Tucker 最優性條件對於給定解成為全域性最優解是必要且充分的（假設一些正則性條件也滿足）。這些 KKT 條件在此列出，因為它們適用於 GLPK。數值求解器也使用這些 KKT 條件來估計其浮點計算完成後的精度。GLPK 可以根據要求提供一個人類可讀的報告，其中包含 KKT 條件，以及使用單純形或內點求解器獲得的任何解。

KKT 計算

GLPK 提供了lpx_check_kkt例程來計算和解釋當前基本解的 KKT 最優性條件。此呼叫填充一個 C 結構LPXKKT例項，從中可以恢復特定資訊。它的使用在官方 GLPK API 手冊中進行了說明，並且呼叫本身也在本維基百科中進行了描述。

KKT 報告

GLPKglp_print_sol和glp_print_ipt呼叫列印一個包含解和該解的 KKT 最優性條件的報告。GLPSOL--output選項也顯示了純 LP（非 MIP）問題的相同資訊（用法不受限制）。

glpsol ... --output file.out

KKT 條件最常用於估計不精確浮點運算對報告解的質量的影響（假設沒有使用精確運算）。此處給出的描述有意簡短——有關詳細資訊，請參閱官方 GLPK API 手冊。共有四個報告測試，標記為KKT.PE到KKT.DB。顯示了一個典型的報告——在本例中是乾淨的！

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.DE: max.abs.err = 0.00e+00 on column 0
        max.rel.err = 0.00e+00 on column 0
        High quality

KKT.DB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

以下三個表格可用於閱讀 KKT 報告。第一個表格中給出的數學表示式在此處進行了詳細描述。

要求	數學上	解釋
`KKT.PE`	$A\mathbf {x} =b$	原始變數滿足原始問題
`KKT.PB`	$\mathbf {x} \geq 0$	非基本變數滿足邊界約束
`KKT.DE`	$A^{\top }\pi +\lambda =c$	目標函式梯度是約束平面法向量的特定線性組合
`KKT.DB`	$\lambda \geq 0$	原始約束阻止解沿著目標函式梯度“移動”

屬性	解釋
`max.abs.err`	最大絕對誤差
`max.rel.err`	最大相對誤差

質量	字元	解釋
`高質量`	`H`	高質量
`中等質量`	`M`	中等質量
`低質量`	`L`	低質量
各種報告	`?`	原始或對偶解錯誤或不可行

上面的char列指的是 GLPK 中包含的字元值LPXKKTC 結構體。

解釋

對於給定問題，如果縮放有效，GLPK 4.45 API 手冊指出，“如果所有指標都顯示高質量或中等質量……使用者可以確信獲得的基本解相當準確。”

整數可行性報告

前兩個 KKT 條件KKT.PE和KKT.PB也可以為混合整數規劃的解計算，並用於調查所得解的數值精度。僅這兩項測試不能保證最優性，但求解器將知道分支定界樹是否已遍歷完。有關詳細資訊，請參見前面的部分。

GLPKglp_print_mip呼叫列印一個包含解和該解的整數可行性條件的報告。GLPSOL--output選項可用於顯示 MIP 問題的此資訊（用法不受限制）。

glpsol ... --output file.out

還要注意 GLPSOL 選項--nomip，它允許透過刪除整數限制來將 MIP 問題作為純 LP 求解。

資訊性 API

以下函式可用於直接收集資訊（應優先於正則表示式文字檔案）

API	註釋
`glp_get_row_prim`	檢索行原始值
`glp_get_row_dual`	檢索行對偶值
`glp_get_row_stat`	檢索行狀態
`glp_get_row_lb`	檢索行下界
`glp_get_row_ub`	檢索行上界
`glp_get_col_prim`	檢索列原始值
`glp_get_col_dual`	檢索列對偶值
`glp_get_col_stat`	檢索列狀態
`glp_get_col_lb`	檢索列下界
`glp_get_col_ub`	檢索列上界
`glp_get_obj_coef`	檢索目標係數或常數項
`lpx_check_kkt`	計算 KKT 最優性條件並填充`LPXKKT`C 結構體

以下函式應生成人類可讀的報告

API	註釋
`glp_print_ranges`	列印人類可讀的靈敏度分析報告
`glp_print_sol`	列印人類可讀的KKT 條件，以及單純形 LP 解
`glp_print_ipt`	列印人類可讀的KKT 條件，以及內點 LP 解
`glp_print_mip`	列印人類可讀的整數可行性報告，以及 MIP 解

自適應使用

幾個創新專案在自適應環境中使用 GLPK 解資訊。一次執行的結果用於生成下一個模型，依此類推，直到達到某個預定的條件。

注意：需要更多詳細資訊。

參考資料

↑ Murtagh, Bruce A (1981). 高階線性規劃：理論與實踐. 紐約，美國：McGraw-Hill. ISBN 0-07-044095-6.

請求：如果有人開發了一些指令碼用於解析人類可讀的報告，他們可以將其新增到此頁面或釋出到[help-glpk]列表，以便在此處包含。

[1] Murtagh, Bruce A (1981). 高階線性規劃：理論與實踐. 紐約，美國：McGraw-Hill. ISBN 0-07-044095-6.

[1]