GNU 線形計画法キット

GNU線形計画キット( GLPK ) は、大規模線形計画(LP)、混合整数計画(MIP)、およびその他の関連問題を解決することを目的としたソフトウェア パッケージです。これは、 ANSI Cで記述され、呼び出し可能なライブラリの形式で編成されたルーチンのセットです。このパッケージはGNU プロジェクトの一部であり、 GNU 一般公衆利用許諾書に基づいてリリースされています。

GLPK は、非整数問題に対しては改訂単体法と主双対内点法を使用し、 (混合)整数問題に対しては 分岐限定アルゴリズムとGomory の混合整数カットを使用します。

GLPK は、モスクワ航空研究所の Andrew O. Makhorin (Андрей Олегович Махорин) によって開発されました。最初の一般公開は 2000 年 10 月でした。

• バージョン 1.1.1 には、改訂された主単体アルゴリズムと双対単体アルゴリズムのライブラリが含まれていました。
• バージョン 2.0 では、主双対内点法の実装が導入されました。
• バージョン 2.2 では、混合整数問題の分岐限定法による解決が追加されました。
• バージョン 2.4 では、GLPK/L モデリング言語の最初の実装が追加されました。
• バージョン 4.0 では、GLPK/L がAMPLモデリング言語のサブセットである GNU MathProg モデリング言語に置き換えられました。

バージョン 4.0 以降、GLPK の問題は、GLPK でのみ使用されるAMPLモデリング言語のサブセットであるGNU MathProg (GMPL)を使用してモデル化できます。ただし、GLPK は他のプログラミング言語から呼び出されることが多いです。次のラッパーが存在します:

• Julia ^[2]とJuMPモデリングパッケージ^[3]
• Java （ OptimJを使用）^[4]

Wikibooks にはGLPKに関する本があります。

• 沖英治（2012年）。通信ネットワークのための線形計画法とアルゴリズム：ネットワーク設計、制御、管理の実践ガイド。CRC Press。ISBN 978-1-4665-5264-7。この本では GLPK のみを使用しており、多数の例が含まれています。

• GLPK公式サイト
• GLPK ウィキブック