GLPK/GMPL (MathProg)

GNU MathProg 是一種高階語言，用於建立 數學規劃 模型。 MathProg 專門針對 GLPK，但類似於 AMPL 的一個子集。 MathProg 也可稱為 GMPL（GNU 數學規劃語言），這兩個術語可以互換使用。

詳細的示例可以在此頁面下方專門的子頁面中找到，按其問題域進行分組。 相反，此頁面提供了一個概述並提供了一個簡短的示例。

官方文件

the official GLPK documentation filedoc/gmpl.pdf包含 MathProg 語言的完整參考。 因此，此處不會重複這些內容。 檢視 獲取 GLPK。

Fourer、Gay 和 Kernighan（2002）

來自這本關於 AMPL 建模語言的經典書籍（第二版）的章節現在可以下載： http://www.ampl.com/BOOK/download.html

作者 Robert Fourer writes（2012 年 8 月）："第 1-10 章也可以作為 GMPL（GNU MathProg）的介紹，儘管在細節上存在差異。"

簡短示例

以下 MathProg 示例實現線性約束最佳化模型

最大化	$0.6x_{1}+0.5x_{2}\,$
受制於	$x_{1}+2x_{2}\leq 1$
	$3x_{1}+x_{2}\leq 2$

在此模型中，沒有要求 $x_{1}$ 和 $x_{2}$ 為非負數。

# 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;

要使用 GLPK 解決此模型，請將上述文字儲存為short.mod然後呼叫

$ glpsol --math short.mod

您應該獲得 $x_{1}=0.6$ 和 $x_{2}=0.2$ 作為 GLPK 求解器終端輸出的一部分。

同一模型使用 GLPK 庫呼叫 進行編碼（需要 C 程式設計）。 同樣的問題顯示在多個 問題格式 中。

官方 GLPK 示例

theexamples官方 GLPK 發行版中的目錄包含大約 60 個 MathProg（以及一些應用程式程式設計）示例

• sample MathProg model (*.mod) files — with and without embedded data
• sample MathProg data (*.dat) files — external data
• sample database (*.dbf) files — table-based external data
• sample data (*.csv) files — table-based external data

注意 下載 GLPK tarball 的說明。

以下是作為官方 GLPK/MathProg 示例一部分的運輸 MathProg LP 模型。 MathProg 模型包含三個（3）個組成部分，即：（1）模型，（2）資料和（3）報告（即後處理） - 可選。

# A TRANSPORTATION PROBLEM
#
# This problem finds a least cost shipping schedule that meets
# requirements at markets and supplies at factories.
#
#  References:
#              Dantzig G B, "Linear Programming and Extensions."
#              Princeton University Press, Princeton, New Jersey, 1963,
#              Chapter 3-3.

set I;
/* canning plants */

set J;
/* markets */

param a{i in I};
/* capacity of plant i in cases */

param b{j in J};
/* demand at market j in cases */

param d{i in I, j in J};
/* distance in thousands of miles */

param f;
/* freight in dollars per case per thousand miles */

param c{i in I, j in J} := f * d[i,j] / 1000;
/* transport cost in thousands of dollars per case */

var x{i in I, j in J} >= 0;
/* shipment quantities in cases */

minimize cost: sum{i in I, j in J} c[i,j] * x[i,j];
/* total transportation costs in thousands of dollars */

s.t. supply{i in I}: sum{j in J} x[i,j] <= a[i];
/* observe supply limit at plant i */

s.t. demand{j in J}: sum{i in I} x[i,j] >= b[j];
/* satisfy demand at market j */

solve;

# Report / Result Section (Optional)
printf '#################################\n';
printf 'Transportation Problem / LP Model Result\n';
printf '\n';
printf 'Minimum Cost = %.2f\n', cost;
printf '\n';

printf '\n';
printf 'Variables  (i.e. shipment quantities in cases ) \n';

printf 'Shipment quantities in cases\n';
printf 'Canning Plants  Markets   Solution (Cases) \n';
printf{i in I, j in J}:'%14s %10s %11s\n',i,j, x[i,j]; 
printf '\n';

printf 'Constraints\n';
printf '\n';
printf 'Observe supply limit at plant i\n';
printf 'Canning Plants Solution Sign  Required\n';
for {i in I} {
 printf '%14s %10.2f <= %.3f\n', i, sum {j in J} x[i,j], a[i];
   }

printf '\n';
printf 'Satisfy demand at market j\n';
printf 'Market Solution Sign  Required\n';
for {j in J} {
 printf '%5s %10.2f >= %.3f\n', j, sum {i in I} x[i,j], b[j];
   }

data;

set I := Seattle San-Diego;

set J := New-York Chicago Topeka;

param a := Seattle     350
           San-Diego   600;

param b := New-York    325
           Chicago     300
           Topeka      275;

param d :              New-York   Chicago   Topeka :=
           Seattle     2.5        1.7       1.8
           San-Diego   2.5        1.8       1.4  ;

param f := 90;

end;

此頁面上可以看到有關各種輸入和輸出（例如 csv、excel 和資料庫（即 access (mdb) 和 SQlite））的示例 [| 10 個你可能想要使用 GLPK 的理由..]

超大型模型

某些型別的超大型 MathProg 模型可能需要很長時間才能解析，可能需要數小時。 例如，一個大型模型可能包含 50 萬個圖邊。 GLPK MathProg 翻譯器是非最佳化的——這意味著它無法在 解析過程 中識別可行的快捷方式。 不過，在某些情況下，可以重新構建 MathProg 模型以解決特定的瓶頸，但建模者首先需要了解解析機制。 在 2011 年 5 月的 thread 中，GLPK 作者 Andrew Makhorin 建議

"MathProg 翻譯器並非旨在（按設計）處理超大型模型。 在這種情況下，最好使用 GLPK API 或使用專門的程式或指令碼生成模型資料，例如以 GLPK LP 格式。"(語法已更正)

也就是說，如果 MathProg 翻譯器完成，則生成的模型將令人滿意。 此外，MathProg 翻譯器通常不受記憶體限制，因此在夜間執行解析作業可能會提供一種可接受的策略。

模型翻譯緩慢

模型已成功重構，解析時間縮短了兩個數量級（從約 15 小時縮短到 9 分鐘）。開源的 OSeMOSYS 能源模型參加了聯合國競賽，並取得了這一成果。 速度提升涉及用包含元組的集合上的扁平遍歷替換巢狀集合遍歷。由於原始集合語義中存在近乎一對一的關聯，因此這種修改後的方法成為可能。此外，其他集合遍歷被完全替換為使用屬性。結論是，應儘可能避免巢狀集合迭代，因為這些迭代會極大地擴充套件要處理的模型空間的維度和大小。此外，在設計和實現模型時，請仔細考慮 MathProg 翻譯器將如何構建你的問題例項。

故障排除

如果在 MathProg 模型中遇到問題，可以透過指定 GLPSOL 選項進行進一步調查--nopresol停用 LP 預求解器，以及--output filename.out將最終解寫入文字檔案。

如果收到訊息 "PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION"，則在解檔案中查詢違反其邊界的變數。這應該可以讓你確定哪些約束是矛盾的，以及哪些調整可能導致可行的系統。

背景資料

Tommi Sottinen 關於 運籌學 和 GPLSOL 的課程筆記 為 MathProg 程式設計提供了極佳的入門介紹。