GLPK/GMPL 檔案處理步驟

本頁面描述 GLPK 處理用 GMPL（也稱為 MathProg）編寫的模型時所採取的步驟。

處理步驟

GLPK 透過一系列步驟求解模型。

模型部分翻譯

GMPL 檔案的模型部分被解析，並建立描述不同物件（如變數、約束和表示式）的內部結構。此階段由函式執行glp_mpl_read_model.

資料部分翻譯

模型檔案的資料部分用於初始化引數和集合。如果資料部分包含在模型檔案中，則此階段由函式執行glp_mpl_read_model. 如果提供了資料檔案（可選），則此階段由函式執行glp_mpl_read_data.

模型生成

在此階段，模型中直至 GMPL solve 語句的語句和表示式都會被求值。此階段由函式執行glp_mpl_generate. 模型生成可能在計算上很昂貴，使用者應該預期生成大型或複雜模型的過程需要時間。

約束本身將根據以下規則進行標準化

原始形式	標準形式
$ax+b\geq cy+d$	$ax-cy\geq d-b$
$ax+b\leq cy+d$	$ax-cy\leq d-b$
$ax+b=cy+d\,\!$	$ax-cy=d-b\,\!$
$c\leq ax+b\leq d$	$c-b\leq ax\leq d-b$

對偶值使用約束的標準形式進行計算。這意味著，在以下示例中，c2的對偶值將相對於c1的對偶值取相反符號，用於否則等效的約束公式

s.t. c1 : 3 * z = 1;
s.t. c2 : 1 = 3 * z;

因此，在解釋非標準約束的對偶值時需要謹慎。反之，良好的做法建議在實際情況下使用標準形式。

模型構建

建立求解器的例項問題。此階段由函式執行glp_mpl_build_prob. 如果沒有在前面呼叫glp_mpl_generate.

求解

透過呼叫適當的求解器來嘗試求解：單純形、內點或 MIP。

求解後處理

求解器呼叫的結果被轉移回 GMPL 變數和約束。模型檔案中 solve 語句之後的語句都會被執行。此階段由函式執行glp_mpl_postsolve.

進一步學習

更多細節可以透過檢查以下內容獲得：

• 函式glp_main在實現檔案src/glpapi19.c(截至 GLPK 4.45)
• 第 3.2 章 用於處理 MathProg 模型的例程 中的示例doc/glpk.pdf來自原始碼分發。

預先設定

使用 GLPSOL 時，無法指定可行（但可能是次優）的起始解 - 但此功能在使用 GLPK API 進行程式設計時受支援，使用 回撥掛鉤 的分支定界演算法。