GLPK/Add-Ons

此頁面描述 GLPK 的“附加元件”——包括 GLPK 程式碼庫的非官方擴充套件，以提供一些特殊功能。因此，這些擴充套件需要合適的編譯環境。

BAK：分支定界分析工具包

使用 BAK 生成的分支定界樹，並使用 gnuplot 渲染

BAK 是用於分析 GLPK 和其他求解器的分支定界行為的工具。 BAK 隨 GPL 2.0 許可證和 CPL 1.0 許可證一起分發——使用者可以選擇使用哪種許可證。

將 BAK 新增到 GLPK

可以使用以下方法下載最新的 BAK 版本

svn checkout https://projects.coin-or.org/svn/CoinBazaar/projects/BAK

可以在 https://projects.coin-or.org/CoinBazaar/browser/projects/BAK/ 檢視原始碼。

BAK 在以下目錄中提供了一些針對 GLPK 的修補原始檔bak/interfaces/GLPK. 首先將這些檔案複製到正常的 GLPK 原始碼目錄，然後重新構建 GLPK（參見章節 編譯 GLPK）。

使用

修改後的獨立求解器 GLPSOL 會寫入一個包含分支資訊的檔案。此檔案的名稱使用命令列選項指定--bakfile, 例如

glpsol --bakfile tsp.bak -m tsp.mod

該檔案包含有關建立的節點、分支過程、遇到的整數不可行性和執行時進度的資訊。該檔案格式在 [1] 中有說明。例如，該檔案可能以以下幾行開頭。

#SOLVER: GLPK
#PROBLEM: (null)
0.002000 branched 1 0 M 6030.000000 6.466667 32
0.002000 candidate 2 1 L
0.002000 candidate 3 1 R
0.004000 branched 2 1 L 6030.000000 6.466667 30
0.004000 candidate 4 2 L
0.004000 candidate 5 2 R
0.006000 branched 4 2 L 6069.000000 7.533333 32
0.006000 candidate 6 4 L
0.006000 candidate 7 4 R
0.008000 branched 7 4 R 6069.000000 7.266667 30
0.008000 candidate 8 7 L
0.008000 candidate 9 7 R
0.009000 infeasible 9 7 R
...

可以使用 python 指令碼建立中間檔案，以便使用 gnuplot 視覺化這些資訊

python bak/BAK_visual.py --all tsp.bak

可以使用 PNG 檔案檢視器（例如 evince）檢視生成的檔案

evince tree_alt.004.png

丹齊格-沃爾夫分解

丹齊格-沃爾夫分解 是一種將結構適當的 LP 問題分解為子問題的方法——然後分別解決這些子問題，通常是並行解決。基礎約束矩陣需要某種形式的塊結構。該技術最初是在 1960 年提出的，鑑於廉價的多核個人計算機的出現，它引起了人們的重新興趣。

該 丹齊格-沃爾夫求解器專案 現在託管在 SourceForge 上，提供了使用 GLPK 的丹齊格-沃爾夫的通用並行實現。該程式碼由 Joey Rios 編寫。第一個公開發布版本 1.0 於 2010 年 10 月 15 日上傳。

該實現使用 Pthreads 執行緒管理庫。GLPK 需要進行少量修改才能允許其併發執行。因此，GLPK 的全部內容都包含在丹齊格-沃爾夫求解器專案的程式碼庫中。除了 Pthreads 之外，不需要其他專業庫。

該程式碼已成功構建在 Mac OS X 10.5 和 10.6、Red Hat Enterprise Linux 以及透過 cygwin 的 Windows XP 上。

作者希望這個工具能為丹齊格-沃爾夫分解的進一步研究提供一個起點。事實上，雖然跨多個領域的許多論文都利用了 DW，但這可能是唯一提供 DW 原始碼供開放測試和開發的專案。

該軟體有一些限制。截至 2010 年 10 月，只能使用 LP 公式，子問題必須是有界的。也可能存在錯誤。

建模者為主問題和每個子問題提供 CPLEX LP 輸入檔案。還需要一個簡單的引導檔案，該檔案告訴命令列工具所有內容在哪裡。該程式碼庫包含從教科書和網站上獲取的或由作者開發的幾個 DW 示例。

有關一般情況下和平行計算下丹齊格-沃爾夫分解的評估，請參見 Tebboth (2001)。 有關空中交通管制應用程式，請參見 Rios 和 Ross (2010)。