跳轉到內容

GLPK/互操作性

Add links
來自 Wikibooks，開放世界中的開放書籍

在本例中，互操作性是指在 GLPK 下轉換和/或使用常見的線性及混合整數問題規範格式的能力。這些格式用於表示和歸檔問題例項。問題格式的概念不應與高階建模語言（如 GLPK MathProg）混淆。本頁還介紹了 GLPK 提供的解恢復格式，並提供有關機器處理 GLPK 輸出的資訊。

概述

[編輯 | 編輯原始碼]

GLPK 可以輕鬆地輸入和輸出各種問題規範格式中的問題

  • CPLEX LP 格式（包括 MIP 問題）
  • MPS 格式，分為固定（舊）和自由（現代）兩種變體
  • 自定義的DIMACS 類格式，名為GLPK 格式。

這意味著 GLPK 可以用來為其他求解器建立問題。並且可以從其他來源獲取問題，並將它們重新格式化或解決。此功能可透過 GLPSOL 和 GLPK 可呼叫庫實現。事實上，一些使用者僅將 GLPK 用於其模型生成和問題重新格式化功能，而從未實際呼叫底層求解器。

GLPK 無法在底層格式規範提供此功能的情況下，將結果寫回這些格式。使用者必須依賴於本機 GLPK 解輸出。GLPK 目前也不支援任何基於XML 的最佳化格式[1]，包括作為COIN-OR OS（最佳化服務）專案的一部分而開發的格式。

此外，GLPK 提供了幾個圖 讀取和寫入例程，它們使用 DIMACS 團/著色格式，以及自定義 GLPK 純文字格式。這些 API 例程目前不可透過 GLPSOL 使用，並且不再討論。

早期版本的 GLPK 支援 OPB 偽布林格式。

以下副檔名約定通常適用

格式 副檔名 評論
CPLEX LP .lp
MPS .mps 固定和自由
GLPK .glp  .glpk

官方 GLPK 文件提供了對每個受支援格式的完整詳細資訊。

最後，本頁包含一個敏感性分析示例，儘管它並不是真正的互操作性問題。敏感性分析解釋鍵在glp_print_ranges 條目中給出。

GLPSOL 用法

[編輯 | 編輯原始碼]

GLPSOL 提供了方便的命令列用法來實現互操作性。從 GLPSOL 的幫助訊息開始是一個很好的起點。

下表總結了相關的互操作性選項（MathProg 列是為了完整性而包含的）：[2]

CPLEX LP MPS 固定 MPS 自由 GLPK MathProg
讀取 --lp --mps --freemps --glp --math
寫入 --wlp 檔名 --wmps 檔名 --wfreemps 檔名 --wglp 檔名 不可行

如上所示，通常無法從低階問題格式建立高階模型。也就是說，CPLEX LP 格式是最人性化的。

以下示例讀取現有convert.lpCPLEX LP 格式檔案，並輸出一個 GLPK 格式檔案，不求解模型。在本例中，--check選項阻止執行模型。

$ glpsol --check --wglp convert.glp --lp convert.lp

GLPSOL 用於解捕獲的選項包括

可列印格式 純文字格式
恢復 --output 檔名 --write 檔名

可列印格式旨在供人類理解。純文字格式用於機器處理。兩種格式均不代表已建立的標準。還可以使用--log選項將終端輸出的副本寫入檔案。因此

$ glpsol --output example.out --log example.log --math example.mod

GLPSOL 提供的相同功能也可透過 GLPK 可呼叫庫的 API 例程獲得。

同樣，官方 GLPK 文件提供了對每個格式的完整詳細資訊。

機器處理 GLPK 輸出

[編輯 | 編輯原始碼]

使用者可能希望自動處理來自 GLPK 的輸出。但是 GLPK 無法生成常見的機器可解析格式，如CSV（逗號分隔值）或XML 或基於這兩種協議的專用方言。相反，GLPK 維護者建議

"要從計算機程式訪問 GLPSOL 找到的解，可以將模型寫入--wglp選項，將解寫入--write選項。行和列的排序在兩個檔案中都是相同的。這足以獲得所有必要的資訊。（我想在這裡做的唯一改進是使用 DIMACS 類格式來儲存解檔案。）" 來源：[help-glpk], 19 Jan 2011，語法已更正，強調部分已新增。

請參閱本頁的其他位置，瞭解來自這兩個 GLPSOL 選項的代表性輸出。

相同的輸出也可以使用適當的 API 呼叫生成，即glp_write_sol, glp_write_ipt, glp_write_mip和glp_write_prob.

簡短示例

[編輯 | 編輯原始碼]

本節使用short.mod模型，它首先在MathProg 頁面上介紹。將以下模型儲存到名為short.mod. 

# short example
var x1;
var x2;
maximize obj: 0.6 * x1 + 0.5 * x2;
s.t. c1: x1 + 2 * x2 <= 1;
s.t. c2: 3 * x1 + x2 <= 2;
solve;
display x1, x2;
end;

敏銳的讀者可能注意到，此模型不包含高階 MathProg 語言功能，因此看起來很像問題格式（solve和display語句除外）。

接下來給出了一些呼叫和結果。此練習還提供了一個對這些各種格式的有用視覺比較。

CPLEX LP 格式

[編輯 | 編輯原始碼]
$ glpsol --check --wlp short.lp --math short.mod 

\* Problem: short *\

Maximize
 obj: + 0.6 x1 + 0.5 x2

Subject To
 c1: + x1 + 2 x2 <= 1
 c2: + 3 x1 + x2 <= 2

Bounds
 x1 free
 x2 free

End

MPS 固定格式

[編輯 | 編輯原始碼]
$ glpsol --check --wmps short.mps --math short.mod 

* Problem:    short
* Class:      LP
* Rows:       3
* Columns:    2
* Non-zeros:  6
* Format:     Fixed MPS
*
NAME          short
ROWS
 N  obj
 L  c1
 L  c2
COLUMNS
    x1        obj                0.6   c1                   1
    x1        c2                   3
    x2        obj                0.5   c1                   2
    x2        c2                   1
RHS
    RHS1      c1                   1   c2                   2
BOUNDS
 FR BND1      x1      
 FR BND1      x2      
ENDATA

MPS 自由格式

[編輯 | 編輯原始碼]
$ glpsol --check --wfreemps short.mps --math short.mod 

* Problem:    short
* Class:      LP
* Rows:       3
* Columns:    2
* Non-zeros:  6
* Format:     Free MPS
*
NAME short
ROWS
 N obj
 L c1
 L c2
COLUMNS
 x1 obj 0.6 c1 1
 x1 c2 3
 x2 obj 0.5 c1 2
 x2 c2 1
RHS
 RHS1 c1 1 c2 2
BOUNDS
 FR BND1 x1
 FR BND1 x2
ENDATA

GLPK 格式

[編輯 | 編輯原始碼]
$ glpsol --check --wglp short.glp --math short.mod 

p lp max 3 2 6
n p short
n z obj
i 1 f
n i 1 obj
i 2 u 1
n i 2 c1
i 3 u 2
n i 3 c2
j 1 f
n j 1 x1
j 2 f
n j 2 x2
a 0 1 0.6
a 0 2 0.5
a 1 1 0.6
a 1 2 0.5
a 2 1 1
a 2 2 2
a 3 1 3
a 3 2 1
e o f

GLPSOL 輸出格式

[編輯 | 編輯原始碼]

請在此處檢視有關KKT 最優性條件的資訊。

$ glpsol --output short.out --math short.mod

Problem:    short
Rows:       3
Columns:    2
Non-zeros:  6
Status:     OPTIMAL
Objective:  obj = 0.46 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 obj          B           0.46                             
     2 c1           NU             1                           1          0.18 
     3 c2           NU             2                           2          0.14 

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           B            0.6                             
     2 x2           B            0.2                             

Karush-Kuhn-Tucker optimality conditions:

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

End of output

GLPSOL 寫入格式

[編輯 | 編輯原始碼]
$ glpsol --write short.sol --math short.mod

3 2
2 2 0.46
1 0.46 0
3 1 0.18
3 2 0.14
1 0.6 0
1 0.2 0

GLPSOL 敏感性分析

[編輯 | 編輯原始碼]

有關表頭的資訊，請參見此處。

$ glpsol --ranges short.rng --math short.mod

GLPK 4.45 - SENSITIVITY ANALYSIS REPORT                                                                         Page   1

Problem:    short
Objective:  obj = 0.46 (MAXimum)

   No. Row name     St      Activity         Slack   Lower bound       Activity      Obj coef  Obj value at Limiting
                                          Marginal   Upper bound          range         range   break point variable
------ ------------ -- ------------- ------------- -------------  ------------- ------------- ------------- ------------
     1 obj          BS        .46000       -.46000          -Inf           -Inf      -1.00000        .      c1
                                            .               +Inf         .46000          +Inf          +Inf

     2 c1           NU       1.00000        .               -Inf           -Inf       -.18000          -Inf
                                            .18000       1.00000           +Inf          +Inf          +Inf

     3 c2           NU       2.00000        .               -Inf           -Inf       -.14000          -Inf
                                            .14000       2.00000           +Inf          +Inf          +Inf

GLPK 4.45 - SENSITIVITY ANALYSIS REPORT                                                                         Page   2

Problem:    short
Objective:  obj = 0.46 (MAXimum)

   No. Column name  St      Activity      Obj coef   Lower bound       Activity      Obj coef  Obj value at Limiting
                                          Marginal   Upper bound          range         range   break point variable
------ ------------ -- ------------- ------------- -------------  ------------- ------------- ------------- ------------
     1 x1           BS        .60000        .60000          -Inf           -Inf        .25000        .25000 c2
                                            .               +Inf           +Inf       1.50000       1.00000 c1

     2 x2           BS        .20000        .50000          -Inf           -Inf        .20000        .40000 c1
                                            .               +Inf           +Inf       1.20000        .60000 c2

End of report

參考資料

[編輯 | 編輯原始碼]
  1. ↑ Fourer, Robert; Lopes, Leo; Martin, Kipp (2005), "LPFML：線性與整數規劃的 W3C XML 模式", INFORMS 計算雜誌, vol. 17, no. 2, pp. 139–158, doi:10.1287/ijoc.1040.0120
  2. ↑ 已過時的選項 --wcpxlp 等效於 --wlp。
取自 “https://wikibook.tw/w/index.php?title=GLPK/Interoperability&oldid=3421278”
華夏公益教科書