2012-04-29 [長年日記]
λ. MPSファイルのフォーマットは酷すぎる
線形計画(LP)や混合整数計画(MIP)の問題の記述に標準的に使われているMPSというファイル形式があるのだけど、そのフォーマットが酷すぎて呆れた話。
経緯
MIPLIB2010の簡単な問題ということで、enlight13 を色々なソルバに食わせて遊んでいたら、GurobiとSCIPは解を見つけるのに、自作ソルバは解がないと言ってきて、どんなバグを埋め込んでしまったかとかなり焦った。 焦ってしばらくバグ探しをした後に、ふとGLPKでも解いてみると、GLPKも解がないと言ってくる。それで、自作ソルバに食わせるためにGLPKでファイルをMPSファイルからLPファイルに変換していたのを思い出し、GLPKのMPSファイルの解釈がGurobiやSCIPと違うのではないかと疑った。 GLPKで変換したファイルをGurobiやSCIPに解かせて解がないという結果になるのを確認。さらに色々見ていると、GLPKのログメッセージでは変数は全部binaryなことになっているけれど、Gurobiの出力した解をみてみると2とかになっているのがある。これだ！
分かったこと
それで、「GLPK MPS bug」で検索してみると、 Re: [Bug-glpk] GLPK 4.46 fails to find solution with enlight13.mps というメールを発見し、原因箇所が判明。件のファイルのBOUNDSの指定に問題があるらしい。
ただ、それだけだと、GurobiやSCIPと解釈が違う理由は分からなかったので、MPSファイルについてさらに調べてみる。 すると、CPLEX では Special Records in MPS Files: ILOG CPLEX Extensions によれば、「MARKERで整数変数を指定する場合、その変数の範囲指定がBOUNDSセクションに存在しない場合には、範囲は[0,1]になる」ということらしいが、その辺りが解釈が違っているのが分かった。
問題のMPSファイルではBOUNDSセクションで変数の下限のみしか指定していなかった。GLPKの実装は、範囲をまず[0,1]で初期化した上で、BOUNDSセクションに記述された上下限でそれらを上書きするという実装になっていたため、上限は1のままになってしまっていた。 それに対して、GurobiやSCIPはどうも下限だけとはいえ範囲が指定されているので[0,1]というデフォルトはそもそも用いないようだ。 ついでに、lp_solve の MPS file format によると、lp_solveはBOUNDSセクションで下限だけでも指定されていればデフォルトは用いないようだが、ただしデフォルトは[0,1]ではなく[0,∞)だとか……
感想
歴史的経緯はあるのだろうけど、元のフォーマットをアドホックに拡張し続けて結果、歪な仕様になった上に、各ツールの解釈が全く違うというひどい状態。こんな腐ったフォーマットが現役で使われているとは酷すぎる……
