線形計画法のテスト問題(netlib)を読み込んで解いてみる

背景と概要

去年くらいからLPソルバを自分で書いてみたりしているのだけど、性能を評価するためのテストケースをどうしようかと思ってWeb検索したりAIに相談したりを何度も繰り返して結局どうしてよいかわからないという状況が続いている。どこかで公開されていたらそれを使うのがベストなのだと思うけど…😖

— Ozy (@ozy4dm) 2023年7月3日

線形計画法のテスト問題が欲しいー！とつぶやいたところ、

まずは古くから使われていて小規模な問題が多い netlib がおすすめです．（ダウンロードは面倒）https://t.co/nPH32zGEHA

Mittelmann 先生が公開しているのは，netlib などの様々なデータセットから比較的難しい問題を選んだものかと思います．https://t.co/YaIjw4sUaN

— 今井義弥 (@imai_yoshiya) 2023年7月3日

と、具体的に教えていただいたので、実際にデータを入手してPuLPを用いて解いてみました。MPSファイルを生成するのに少し手間がかかるので、メモ的に書き残しておきたいと思います。

問題データを手に入れる

データはhttps://www.netlib.org/lp/data/からダウンロードできます。 ただ、データフォーマットが圧縮MPSになっているのでまずこれをMPSファイルに展開する必要があります。

empsというプログラムが必要なので、まずこれを生成します。FortranとCのコードがありますが、私はCの方を使いました。

curl -L -O http://netlib.org/lp/data/emps.c

で入手して、

gcc -o emps emps.c

みたいな感じでコンパイルしてください。実行ファイルができたら、

emps < 圧縮MPSファイル名 > MPSファイル名

という感じで使います。試しにページの一番上にある25fv47というデータを使ってみます。

emps < 25fv47 > 25fv47.mps

みたいにすればOKです。

PuLPで解いてみる

次にこのデータを適当なソルバで解いてみることにします。 今回はPuLPで解いてみました。Pythonがすでに使えるものとして、

pip install pulp

でPuLPを使えるようにしておきます。コードは以下の通りです。第一引数にmpsファイルのパスを取るようにしておきます。

import sys
import pulp

mps_file_path = sys.argv[1]
variables, problem = pulp.LpProblem.fromMPS(mps_file_path)
problem.solve()

たったこれだけ。超簡単ですね！実際に動かしてみると、次のような出力が得られました。

...
最初の方は省略
...
Optimal - objective value 5501.8459
After Postsolve, objective 5501.8459, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 5501.845888 - 1718 iterations time 0.152, Presolve 0.01
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.17   (Wallclock seconds):       0.20

問題データのダウンロード元にあるhttps://www.netlib.org/lp/data/readme:readmeを見ると、次のように書かれていました。

Name       Rows   Cols   Nonzeros    Bytes  BR      Optimal Value
25FV47      822   1571    11127      70477        5.5018458883E+03

ちゃんと解が得られたようです。やったー！

というわけで、この情報を教えてくださったimai_yoshiyaさんと、最初にアドバイスをくださったｵﾉｳｪｲ先生に感謝！！

今後自分のソルバで何か成果が出たら改めてきちんと記事にしたいと思います。

追記

結構面倒だったので、まとめて処理しておきました。 https://github.com/ozy4dm/lp-data-netlib

しかし以下の問題について、データの生成ができていません。

• QAP8
• QAP12
• QAP15
• STOCFOR3

QAP8, QAP12, QAP15については、こちらからジェネレータを手に入れる必要があります。

また、STOCFOR3については実行時にエラーが発生します。トライしてみた結果、以下のようなエラーメッセージが表示されました。

% ./std2mps

 Process TIME file:
       1    TIME          STOCHFOR
      10    ENDATA

 Process CORE file:
       1                                  0.0000                   0.0000
 XXX -  FATAL  - Illegal record in CORE file

 STD2MPS: execution terminated.

解決したら更新しておこうと思いますが、今のところよくわからないのでそのままにしておきます。