GLPK/常見問題解答

GNU 線性規劃工具包常見問題解答

Summary: Frequently Asked Questions about the GNU Linear Programming Kit
Original author: Dr. Harley Mackenzie <hjm@hardsoftware.com>                     

簡介

問. 什麼是 GLPK？

答. GLPK 代表 GNU 線性規劃工具包。GLPK 包是一個用 ANSI C 編寫的例程集，並以可呼叫庫的形式組織起來。此包旨在解決大型線性規劃 (LP)、混合整數線性規劃 (MIP) 和其他相關問題。

GLPK 包包括以下主要元件

• 單純形法的實現，
• 原始對偶內點法的實現，
• 分支定界法的實現，
• 應用程式程式設計介面 (API)，
• GNU MathProg 建模語言（AMPL 的子集），
• GLPSOL，一個獨立的 LP/MIP 求解器。

問. 誰開發和維護 GLPK？

答. GLPK 目前由莫斯科航空學院應用資訊學系安德魯·馬霍林開發和維護。安德魯的電子郵件地址是 <mao@mai2.rcnet.ru>，郵寄地址是俄羅斯莫斯科沃洛科拉姆斯克耶·什., 4 號，莫斯科航空學院，安德魯·奧·馬霍林。

問. GLPK 是如何授權的？

答. GLPK 目前根據 GNU 通用公共許可證 (GPL) 授權。GLPK 是自由軟體；您可以在 GNU 通用公共許可證的條款下重新分發和/或修改它，該許可證由自由軟體基金會發布；無論是版本 2，還是（在您的選擇下）任何更高版本。

GLPK 不根據較小通用公共許可證 (LGPL) 授權，與其他自由 LP 程式碼（如 lp_solve）不同。最顯著的含義是連結到 GLPK 庫的程式碼必須根據 GPL 釋出，而使用 LGPL，連結到庫的程式碼不必根據相同許可證釋出。

問. GLPK 主頁在哪裡？

答. GLPK 主頁是 GNU 網站的一部分，可以在 <http://www.gnu.org/software/glpk/glpk.html> 找到。

問. 我如何下載和安裝 GLPK？

答. GLPK 原始碼分發可以在您最喜歡的 GNU 映象上的子目錄 /gnu/glpk/ 中找到 <http://www.gnu.org/prep/ftp.html>，可以直接從原始碼編譯。

GLPK 包（與所有其他 GNU 軟體一樣）以打包檔案的形式分發。這是一個名為 'glpk-x.y.tar.gz' 的檔案，其中 x 是主版本號，y 是次版本號。

為了準備分發以進行安裝，您應該

1. 將 GLPK 分發檔案複製到某個子目錄。
2. 輸入命令 'gzip -d glpk-x.y.tar.gz' 以解壓縮分發檔案。解壓縮後，分發檔案的名稱將自動更改為 'glpk-x.y.tar'。
3. 輸入命令 'tar -x < glpk-x.y.tar' 以解壓縮分發檔案。執行此操作後，將自動建立子目錄 'glpk-x.y'，它是 GLPK 分發檔案。

解壓縮和解壓縮 GLPK 分發檔案後，您應該配置包並編譯應用程式。編譯的結果是

• 檔案 'libglpk.a'，它是一個庫檔案，包含所有 GLPK 例程的目的碼；以及
• 程式 'glpsol'，它是一個獨立的 LP/MIP 求解器。

完整的編譯和安裝說明包含在分發檔案中包含的 INSTALL 檔案中。

該分發包含適用於 Microsoft Visual C/C++ 版本 6 和 Borland C/C++ 版本 5 的 make 檔案，預設情況下編譯和連結 glpk*.lib 庫檔案、glpk*.dll DLL 檔案和 glpsol.exe 應用程式檔案。從 <http://gnuwin32.sourceforge.net/packages/glpk.htm> 也提供了使用 mingw32 C/C++ 編譯器編譯的 GNU Windows 4.1 二進位制檔案、原始碼和文件。

問. 有 GLPK 郵件列表或新聞組嗎？

答. GLPK 有兩個郵件列表：<help-glpk@gnu.org> 和 <bug-glpk@gnu.org>。

主要討論列表是 <help-glpk@gnu.org>，用於討論 GLPK 的所有方面，包括它的開發和移植。還有一個專門用於報告錯誤的列表 <bug-glpk@gnu.org>。

要訂閱任何 GLPK 郵件列表，請傳送一封主題行僅為“subscribe”的空郵件到相關的 -request 列表。例如，要訂閱主要列表，您需要將郵件傳送到 <help-glpk-request@gnu.org>，郵件正文為空，主題行僅為“subscribe”。

訂閱 GLP 郵件列表的另一種方法是訪問網頁 <http://mail.gnu.org/mailman/listinfo/help-glpk> 和 <http://mail.gnu.org/mailman/listinfo/bug-glpk>。

目前沒有專門針對 GLPK 的新聞組。

問. 誰維護此常見問題解答，我如何為該常見問題解答做出貢獻？

答. 本常見問題解答的現任維護人是 HARD 軟體的哈利·麥肯齊博士，儘管常見問題解答的內容來自許多來源，例如 GLPK 文件、GLPK 郵件存檔和原始內容。

哈利的電子郵件地址是 <hjm@hardsoftware.com>，郵寄地址是澳大利亞維多利亞州紐鎮郵政信箱 8004，HARD 軟體公司。

所有對本常見問題解答的貢獻，例如問題和（最好）答案，應傳送到 <hjm@hardsoftware.com> 電子郵件地址。此常見問題解答版權歸哈利·麥肯齊 2003 所有，並根據與 GLPK 相同的許可證、條款和條件釋出，即 GPL 版本 2 或更高版本。

貢獻不會直接在常見問題解答正文中引用，因為這將變得難以管理且雜亂無章，而是在對本常見問題解答的貢獻者列表中列出。如果您是本常見問題解答中包含的任何資訊的作者，並且您不希望您的內容被包含在內，請聯絡常見問題解答維護者，您的資料將被刪除。此外，如果您沒有被正確地列為本常見問題解答的貢獻者，您的詳細資訊已更改，或者您不希望您的姓名列在貢獻者列表中，請聯絡常見問題解答維護者進行更正。

問. 我在哪裡可以下載此常見問題解答？

答. 最新版本的 GLPK 常見問題解答可以從 <http://www.hardsoftware.com/downloads.php#GLPK+FAQ> 下載，以下格式

• DocBook
• 格式化文字
• Adobe PDF

問. 常見問題解答的貢獻者是誰？

答. 常見問題解答的內容來自以下來源

• 邁克爾·亨內布里
• http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html
• 哈利·麥肯齊，HARD 軟體私人有限公司。
• 安德魯·馬霍林，莫斯科航空學院應用資訊學系

GLPK 函式和功能

問. GLPK 開發的現狀如何？

答. GLPK 正在開發中，目前正在不斷開發中。截至目前版本 4.3，GLPK 是一個基於單純形的求解器，能夠處理最多 100,000 個約束的問題。特別是，它成功地解決了 netlib 中的所有例項（請參閱 GLPK 分發中包含的 bench.txt 檔案）。內點求解器不太健壯，因為它無法處理密集列，有時會因數值不穩定或收斂速度慢而終止。

混合整數規劃 (MIP) 求解器目前基於分支定界，因此它無法解決困難或非常大的問題，可能的實際限制為 100-200 個整數變數。但是，有時它能夠解決最多 1000 個整數變數的更大問題，儘管大小取決於特定問題的屬性。

問. GLPK 與其他 LP 程式碼相比如何？

答. 我認為在非常大規模的例項中，CPLEX 8.0 對偶單純形比 GLPK 單純形求解器快 10-100 倍，當然也更健壯。在許多情況下，對於純 LP 以及 MIP，GLPK 比 lp_solve 4.0 更快、更健壯。請參閱 GLPK 分發 doc 目錄中的 bench.txt 檔案，以瞭解 GLPK netlib 基準測試結果。

您可以在漢斯·米特爾曼的網頁上找到一些 LP 和 MIP 求解器的基準測試，例如 CPLEX、GLPK、lp_solve 和 OSL <http://plato.asu.edu/bench.html>。

問. AMPL 和 GNU MathProg 之間有什麼區別？

答. 在 MathProg 中實現的 AMPL 子集大約對應於 1990 年的 AMPL 狀態，因為它主要基於羅伯特·福雷、大衛·M·蓋伊和布萊恩·W·科尼漢 (1990) 的論文“數學規劃的建模語言”，管理科學，第 36 卷，第 519-554 頁，可以在 <http://users.iems.nwu.edu/~4er/WRITINGS/amplmod.pdf> 找到。

GNU MathProg 翻譯器是作為 GLPK 的一部分開發的。但是，GNU MathProg 可以輕鬆地用於其他應用程式，因為有一組專為在其他應用程式中使用而設計的 MathProg 介面例程。

問. GLPK 支援哪些輸入檔案格式？

答. GLPK 目前可以以三種支援的格式讀取輸入和輸出 LP 模型檔案

• MPS 格式 - 這是一種面向列的、廣泛支援的檔案格式，但人類可讀性差。
• CPLEX 格式 - 這是一種易於閱讀的面向行的格式。
• GNU MathProg - 這是一種類似 AMPL 的數學建模語言。

問. GLPK 提供了哪些介面？

A. GLPK 軟體包實際上是一個 C 語言 API，可以靜態或動態連結到許多程式設計系統中。

目前，GLPK 軟體包中包含三個貢獻的外部介面

• GLPK Java 本地介面 (JNI)
• GLPK Delphi 介面 (DELI)
• GLPKMEX Matlab MEX 介面

在 <http://gottfried.lindner.bei.t-online.de/glpk.htm> 中提供了一個非官方的 Microsoft Visual Basic、Tcl/Tk 和 Java GLPK 介面。

在 CVXOPT 中提供了一個 Python 介面，用於 GLPK 的 LP 求解器，請參閱 <http://abel.ee.ucla.edu/cvxopt/>。

目前正在開發其他語言介面，包括 FAQ 維護者 Harley Mackenzie 博士 <hjm@hardsoftware.com> 正在開發的 Perl 介面。

Q. 在哪裡可以找到一些示例？

A. GLPK 軟體包發行版包含許多示例，這些示例是用 GNU MathProg (*.mod)、C API 呼叫 (*.c)、CPLEX 輸入檔案格式 (*.lpt)、MPS 格式 (*.mps) 以及一些特定旅行商示例 (*.tsp) 編寫的。

所有示例都可以在 GLPK 發行版示例子目錄中找到。

Q. GLPK 的未來計劃是什麼？

A. GLPK 的計劃開發包括改進現有的關鍵 GLPK 元件，例如開發更健壯、更高效的單純形和內點求解器的實現。計劃中的未來 GLPK 增強功能包括實現分支定界求解器、MIP 預處理器、後最優和敏感性分析，以及可能的網路單純形和二次規劃求解器。

Q. 如何報告 GLPK 錯誤？

A. 如果你認為在 GLPK 中發現了錯誤，那麼你應該向 <bug-glpk@gnu.org> 傳送儘可能完整的報告。

Q. 如何為 GLPK 開發做出貢獻？

A. 目前，新的 GLPK 開發補丁應透過電子郵件傳送給 Andrew Makhorin <mao@mai2.rcnet.ru >，並附有足夠的文件和測試程式碼，以解釋補丁的性質、如何安裝它及其使用帶來的影響。在開始進行任何主要 GLPK 開發以納入 GLPK 發行版之前，最好在 GLPK 郵件列表上討論這個想法。

Q. 如何在 UNIX 平臺上編譯和連結 GLPK 應用程式？

A. 為了在 UNIX 平臺上編譯 GLPK 應用程式，編譯器必須能夠包含 GLPK 包含檔案並連結到 GLPK 庫。例如，在 GLPK 系統安裝的系統上

 gcc mylp.c -o mylp -lglpk 

或者如果 GLPK 未安裝，則顯式指定包含檔案和 libglpk.a。

Q. 如何在 Win32 平臺上編譯和連結 GLPK 應用程式？

A. 在 Win32 平臺上，GLPK 作為 Win32 動態連結庫 (DLL) 實現，或者可以靜態連結到 glpk*.lib 檔案。與 UNIX 指示一樣，GLPK 應用程式必須設定指向 GLPK 包含檔案的路徑，如果靜態連結，還需要引用 GLPK 庫。

Q. 如何限制 GLPK 執行時間？

A. 你可以透過 API 例程 lpx_set_real_parm 設定控制引數 LPX_K_TMLIM 來限制計算時間。目前，沒有辦法限制 glpsol 的執行時間，除非更改原始碼並重新編譯特定版本。

GLPK 線性規劃

Q. 什麼是線性規劃，它是如何工作的？

A. 線性規劃是一種數學技術，它是一種解決具有線性項的某些方程組的通用方法。LP 的真正威力在於它們有許多實際應用，並已被證明是一種強大而健壯的工具。

關於 LP 的最佳單一資訊來源是線性規劃 FAQ <http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html>，其中包含有關 LP 和 MIP 的資訊，包括可用的 LP 軟體的綜合列表，以及許多供進一步研究的 LP 參考資料。

Q. 如何確定 LP 解的穩定性？

A. 你可以透過為 glpsol 指定 --bounds 選項來執行敏感性分析，如

 glpsol ... --bounds filename 

在這種情況下，求解器會將分析結果以純文字格式寫入指定的檔名。相應的 API 例程是 lpx_print_sens_bnds() 。

Q. 如何確定哪些約束導致不可行？

A. 找到這樣一組約束的一個簡單方法是逐個刪除約束。如果刪除約束會導致可解問題，則將其拾取並繼續進行下一個約束。在將階段 1 應用於不可行問題後，所有基本的滿足約束都可以刪除。

如果問題具有可行的對偶，那麼執行對偶單純形方法是一種更直接的方法。在最後一次旋轉之後，非基本約束和一個違反的約束將構成一個最小集合。GLPK 單純形表例程將允許你從違反的約束中選擇一個正確的約束。

請注意，需要關閉 GLPK 預處理器才能使上述技術起作用，否則 GLPK 不會保留不可行解的基礎。

此外，在郵件列表存檔中釋出了更詳細的方法，位於 <http://mail.gnu.org/archive/html/help-glpk/2003-09/msg00017.html>。

Q. 檢查和約束有什麼區別？

A. 檢查語句旨在檢查使用者在模型中指定的所有資料是否正確，主要是在 MathProg 模型的資料部分。例如，如果某個引數表示網路中的節點數，則它必須是正整數，這只是在檢查語句中檢查的條件（儘管在這種情況下，可以在引數語句中直接檢查此條件）。請注意，檢查語句是在翻譯器生成模型時執行的，因此它們不能包含變數。

約束是根據變量表達的條件，並在模型完全生成後由求解器解決。如果模型中指定的所有資料都事先正確，則不需要檢查語句，可以省略，而約束是模型的重要組成部分，因此不能省略。

GLPK 整數規劃

Q. 什麼是整數規劃，它是如何工作的？

A. 整數 LP 模型是指其變數被約束為取整數或整數（而不是分數）值的模型。整數規劃比普通線性規劃困難得多，這可能並不明顯，但實際上確實如此，無論是在理論上還是在實踐中。

Q. 什麼是整數最佳化套件 (IOS)？

A. IOS 是一個框架，用於實現基於 LP 鬆弛的隱式列舉方法（如分支定界和分支剪枝）。目前 IOS 只包含基本功能（列舉樹、API 例程和驅動程式），並沒有完整記錄。

Q. 我剛把一個 LP 更改為 MIP，現在它不起作用了？

A. 如果你有一個正在執行的 LP，你將其更改為 MIP 並收到“lpx_integer: optimal solution of LP relaxation required” 204 (==LPX_E_FAULT) 錯誤，你可能在 lpx_integer() 之前沒有呼叫 LP 求解方法 lpx_simplex() 。MIP 例程使用 LP 解作為 MIP 解方法的一部分。

注意：此答案已過時 —lpx_simplex()和lpx_integer()已被棄用，請嘗試glp_iotopt()代替。

Q. 什麼是切割，它們是如何工作的？

A. 假設你有一個 MIP 例項。刪除整型約束會得到 MIP 的 LP 鬆弛。LP 鬆弛的可行集是一個多面體 P，其頂點對應於基本解，這些解可能是非整型的（因為整型約束被刪除）。現在假設你構建了 MIP 可行集的凸包 T。它也是一個多面體（稱為 MIP 多面體）；根據定義，每個頂點都對應於一個基本解，該解是整型的。顯然，T 是 P 的子集。請注意，T 的描述，即定義它的線性不等式組，通常是未知的。如果你找到了 LP 鬆弛的最優解，即 P 的最優頂點，假設為 x，並且 x 不是整型，則必須存在一個稱為切割平面的超平面或切割，它將 x 從 T 中切除（分離）。如果你找到了某個切割 ax >= b，你可以將此不等式（稱為有效不等式）新增到原始 MIP 中；請注意，如果一個不等式是有效的，則每個整型解都滿足它，即它保留 T。理想情況下，切割應該是 T 的一個面，然而，對於許多 MIP 類，很難找到這種面誘導的有效不等式。

歷史上，第一類切割平面是由 Ralph Gomory 提出的。分支剪枝方法是分支定界方法，其中子問題用切割平面加強，這使得可以減小搜尋樹的大小。在網際網路上，你可以找到大量關於分支剪枝方法的報告、論文和書籍。

GLPK 資料庫訪問

Q. 是否可以透過 ODBC 從 Access DB 中讀取一個簡單的標量引數？

A. 標量引數在表語句中不允許使用。但是，你可以定義一個標量引數陣列，例如

  set N; /* parameter names */
  param p{N}; /* parameter values */

從表中讀取 S 和 p{S}，然後在模型中使用 p["test"]。