MPS (フォーマット)

MPS (Mathematical Programming System) は、線形計画法(LP) および混合整数計画法の問題を提示およびアーカイブするためのファイル形式です。

概要

この形式は、初期のIBM LP 製品^[1]にちなんで名付けられ、ほとんどの商用 LP ソルバーの間で事実上の標準ASCII媒体として登場しました。基本的にすべての商用 LP ソルバーはこの形式を受け入れ、オープンソースのCOIN-ORシステムでも受け入れられています。他のソフトウェアでは、MPS ファイルを読み取るためにカスタマイズされたリーダールーチンが必要になる場合があります。ただし、代数モデリング言語の受け入れに伴い、 MPS の使用は減少しています。たとえば、 2011 年 1 月のNEOSサーバー統計によると、提出物の 1% 未満が MPS 形式でしたが、AMPLでは 59.4%、 GAMSでは 29.7%でした。

MPS は列指向であり (モデルを方程式として入力するのではなく)、すべてのモデルコンポーネント (変数、行など) に名前が付けられます。MPS は古い形式であるため、パンチカード用にセットアップされています。フィールドは列 2、5、15、25、40、50 から始まります。MPS ファイルのセクションは、列 1 から始まることで区別される、いわゆるヘッダーカードによってマークされます。歴史的な理由から、ファイル全体では大文字を使用するのが一般的ですが、多くの MPS リーダーは、ヘッダーカード以外のすべてで大文字と小文字の混在を受け入れ、一部のリーダーではどこでも大文字と小文字の混在が許容されます。個々のエンティティ (制約または変数) に選択する名前は、ソルバーにとって重要ではありません。意味のある名前、または後処理コードが読み取りやすい名前を選択する必要があります。

MPS形式

以下は MPS 形式で記述された小さなサンプルモデルです (詳細は以下で説明します)。

名前 TESTPROB
行
 N コスト
 L リム1
 G LIM2
 E MYEQN
コラム
    XONE コスト 1 制限 1 1
    XONE LIM2 1
    YTWO コスト 4 LIM1 1
    YTWO MYEQN -1
    ZTHREE コスト 9 LIM2 1
    ZTHREE MYEQN 1
右
    右辺1 左辺1 5 右辺2 10
    RHS1 MYEQN 7
境界
 アップBND1 XONE4
 LO BND1 YTWO -1
 アップ BND1 YTWO 1
エンデータ

比較のために、同じモデルを方程式指向の形式で書き出したものを次に示します。

最適化する
 コスト: XONE + 4*YTWO + 9*ZTHREE
対象
 LIM1: XONE + YTWO <= 5
 限界2: XONE + ZTHREE >= 10
 MYEQN: - YTWO + ZTHREE = 7
境界
       XONE <= 4
 -1 <= YTWO <= 1
終わり

後述するように、XONE の下限は、指定されていないため、実装に応じて 0 または - 無限大のいずれかになります。奇妙なことに、MPS 形式では最適化の方向が指定されておらず、標準の「デフォルト」方向はありません。一部の LP ソルバーは、特に指示がない場合は最大化しますが、他のソルバーは最小化します。^[2]また、安全性を最優先し、デフォルトがなく、制御プログラムのどこかまたは呼び出しパラメータによって選択を必要とするソルバーもあります。モデルが最小化用に定式化されており、ソルバーが最大化を必要とする場合 (またはその逆)、目的関数のすべての係数を否定することで、2 つのソルバーを簡単に変換できます。目的関数の最適値は、元の最適値の負になりますが、変数の値自体は正しいものになります。一部のプログラムでは、MPS ファイル内での最小化/最大化の指定をサポートしています。

オブジェセンス
 マックス

MPSセクション

NAMEセクションは、1列目から4列目に「名前」という単語が書かれ、15列目から21列目に問題のタイトルが書かれます。^[3]

オプションのOBJSENSEセクションでは、LP問題が最大化問題か最小化問題かを定義します。このセクションは、デフォルトの動作（最小化）が望ましくない場合に特に役立ちます。^[4]

ROWS セクションでは、すべての制約の名前を定義します。列 2 または 3 のエントリは、等号 (=) 行の場合は E、小なり (<=) 行の場合は L、大なり (>=) 行の場合は G、制約のない行の場合は N です。このセクションで指定された行の順序は重要ではありませんが、N とマークされた制約のない行の場合は、最初の行が目的関数として解釈されます。

COLUMNS セクションには、A マトリックスのエントリが含まれます。特定の列のすべてのエントリは連続して配置する必要がありますが、列内ではエントリ (行) の順序は関係ありません。列で指定されていない行は、係数が 0 であるとみなされます。

RHS セクションでは、1 つ以上の右辺ベクトルを定義できます。1 つ以上になることはほとんどありません。上記の例では、RHS ベクトルの名前は RHS1 であり、問題の 3 つの制約行すべてにゼロ以外の値があります。RHS ベクトルで言及されていない行は、右辺がゼロであると見なされます。

オプションのRANGESは行の下限と上限の二重不等式を指定します。^[3]

オプションの BOUNDS セクションでは、個々の変数の下限と上限を指定します。最初の 2 ～ 3 列は、境界タイプを指定します。一般的な境界には、UP、LO、FX、FR、MI、PI などがあります。ここで、UP タイプの境界は、変数に上限が適用されることを意味します。LO タイプの境界は、下限が適用されることを意味します。FX ("固定") の境界タイプは、変数の上限と下限が単一の値に等しいことを意味します。FR ("自由") の境界タイプは、変数に下限も上限もなく、負の値を取ることができることを意味します。そのバリエーションとして、MI は自由負で、上限は 0 ですが下限はありません。PL 境界タイプは、0 から正の無限大までの自由正ですが、これは通常のデフォルトであるため、めったに使用されません。さらに、mps ファイル形式のいくつかの変更では、MIP モデルで使用する境界タイプが存在します。たとえば、BV はバイナリで、0 または 1 です。UI は上位整数、LI は下位整数です。 SC は半連続の略で、変数がゼロになる可能性があるが、そうでない場合は指定された値以上でなければならないことを示します。指定された BOUNDS セットに記載されていない変数は、負でないとみなされます (下限はゼロ、上限はありません)。次に、行ラベルが列 5 ～ 12 にあり、列ラベルが列 14 ～ 22 にあります。境界の値は列 25 ～ 36 にあります。^[4]

MPS標準のいくつかの特殊なケースは、実装によって一貫して処理されません。BOUNDSセクションでは、変数に非正の上限が指定されているが下限が指定されていない場合、その下限はデフォルトでゼロまたは負の無限大になることがあります（また、上限がゼロとして指定されている場合、下限はゼロまたは負の無限大になる可能性があります）。^[5]整数変数に上限が指定されていない場合、その上限はプラスの無限大ではなく1にデフォルト設定されることがあります。

あるいは、一部のMPSソルバーでは、他のカテゴリを使用して機能を拡張できます。たとえば、整数変数をキーワード「MARKER」「INTORG」「Marker」「INTEND」^[4]またはINTEGERなどの別のセクションでマークするIntegralityマーカーなどです。さまざまなソルバー用の他の多くのカスタムカテゴリがあります。^[4]

ENDATAセクションはLP問題の終了を意味します。これは必ずそこになければなりません

制限事項

MPS には多くの制限があります。最適化の方向は指定されませんが、ソルバーによって処理方法が異なります。数値フィールドの幅は 12 文字なので、精度が制限されます。表現は人間が解釈しやすいものではなく、コンパクトでもありません (ただし、列/行の順序情報は保持されるため、LP ソルバーの動作の再現性に役立つことがよくあります)。MPS の代替として制限がなく、ほとんどのソルバーでサポートされているものの 1 つがnl ファイル形式です。

拡張機能

多くの LP 製品には、MPS 形式の拡張機能が含まれています。フリーフォーマットの MPS では、フィールドが元の標準で定義された列を超えることを許可し、固定の列位置の代わりに空白を区切り文字として適用することで、長い名前とより正確なデータが可能になります (これにより、名前の一部として空白を含む一部の MPS ファイルは無効になることに注意してください)。一部の拡張機能には、MPS ファイルに新しい種類のデータを追加することが含まれます (たとえば、客観的な意味、積分要件、二次データ、または高度な MIP モデリング構造を含むセクション)。圧縮された MPSC ファイル形式もあります。^[6] SMPS ^[7]は、特に研究環境で使用されている、確率的計画問題インスタンスを表すために設計された特殊な拡張機能です。

一部の拡張機能は標準化されていませんが、この形式は今でも一般的に使用されています。

参照

線形計画法
MPS ファイル形式 – lp_solve の作者による形式の説明
xMPS – 拡張MPS形式

参考文献

^ IBM、最適化サブルーチンライブラリ、ガイドおよびリファレンス、文書 SC23-0519、IBM^{[リンク切れ‍ ]}
^ ILOG CPLEX 10.0 ファイル形式(PDF)。 2006 年 1 月。p. 28. {{cite book}}:|work=無視されました (ヘルプ)
^ ab Murtagh, Bruce A. (1981). Advanced Linear Programming: Computation and Practice. ニューヨーク; ロンドン: McGraw-Hill International Book Co. pp. 163–166 . 2024年9月27日閲覧。
^ abcd 「Gurobi Optimizer リファレンスマニュアル」。Gurobiドキュメント。Gurobi Optimization, LLC。2024年9 月 27 日閲覧。
^ IBM CPLEX ドキュメント
^ 「EMPS – 圧縮された MPS ファイルの展開」。People.sc.fsu.edu。2005 年 8 月 31 日。2012 年 12 月 23 日時点のオリジナルよりアーカイブ。2013年 1 月 22 日閲覧。
^ 「確率線形計画法の SMPS 形式」 Myweb.dal.ca. 2006-07-11。2013-06-28 にオリジナルからアーカイブ。2014-05-28に取得。

[1] IBM、最適化サブルーチンライブラリ、ガイドおよびリファレンス、文書 SC23-0519、IBM^{[リンク切れ‍ ]}

[2] ILOG CPLEX 10.0 ファイル形式(PDF)。 2006 年 1 月。p. 28. {{cite book}}:|work=無視されました (ヘルプ)

[Murtagh-3] Murtagh, Bruce A. (1981). Advanced Linear Programming: Computation and Practice. ニューヨーク; ロンドン: McGraw-Hill International Book Co. pp. 163–166 . 2024年9月27日閲覧。

[GurobiMPS-4] 「Gurobi Optimizer リファレンスマニュアル」。Gurobiドキュメント。Gurobi Optimization, LLC。2024年9 月 27 日閲覧。

[5] IBM CPLEX ドキュメント

[6] 「EMPS – 圧縮された MPS ファイルの展開」。People.sc.fsu.edu。2005 年 8 月 31 日。2012 年 12 月 23 日時点のオリジナルよりアーカイブ。2013年 1 月 22 日閲覧。

[7] 「確率線形計画法の SMPS 形式」 Myweb.dal.ca. 2006-07-11。2013-06-28 にオリジナルからアーカイブ。2014-05-28に取得。