DISTRICT 37

なにか

OpenOptとGLPKで線形計画問題を解く

最適化問題API OpenOpt

OpenOpt

OpenOptの位置づけがどうもわからん。ソルバーかなと思うとそうではなく、最適化問題に関するAPI群とかフレームワークというのがなんとか腑に落ちる表現かなと思われる。ということでOpenOptを使った線形計画問題を書いてみた。今回はソルバーとしてglpkを使用する。

インストール

必要なのは以下のライブラリ

  • OpenOpt
  • FuncDesinger
  • GLPK
  • CVXOPT

インストールはpipおよびaptから行う。モデルの構築が簡単になるFuncDesingerも合わせてインストールしておくと捗る。glpkとかcvxoptはいわゆる線形計画法のソルバー。OpenOptから呼び出せる。

pip install openopt funcdesinger
apt install python-glkp glpk-utils libglpk-dev

ここまでで必要なライブラリをインストール完了、、、ではなくライブラリに少し小細工が必要となる。LP-OpenOptの利用可能なソルバー一覧を見ると以下のように書いてある

Requires installation glpk + CVXOPT. Ensure CVXOPT setup.py file has line BUILD_GLPK=1 or use software install/update channels like aptitude, apt-get etc

glpkを使うにはCVXOPTとライブラリをリンクしておけという感じらしい。ということで説明通りにやってみる。すでにcxvoptはインストールされていたのでupgradeオプションを使う。きっとOpenOptかglpkをインストールするときに入ったのだろう。ただ、オプションのつけ方はCVXOPTの公式に記載されていた方法を使った。

CVXOPT_BUILD_GLPK=1 pip install cvxopt --upgrade

ここまでで本当に準備完了。

問題

問題は以前にpulpでやった問題と同じものを使う

dragstar.hatenablog.com

書いたコードは下記のとおり

startpointの指定がなんとなく使い勝手が悪い気がする。デフォルトで0から始めてほしいと思うんだけどねぇ。難しい問題なら指定することで少しは早くなるのかな?まぁいいや。それで答えとアウトプットは以下の通りとなった。

------------------------- OpenOpt 0.5501 -------------------------
solver: glpk   problem: unnamed    type: LP   goal: max
 iter   objFunVal   log10(maxResidual)   
    0  0.000e+00            -100.00 
GLPK Simplex Optimizer, v4.52
3 rows, 2 columns, 6 non-zeros
*     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
*     3: obj =  -2.700000000e+04  infeas =  0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
    1  0.000e+00            -100.00 
istop: 1000 (optimal)
Solver:   Time Elapsed = 0.01   CPU Time Elapsed = 0.0
objFunValue: 27000 (feasible, MaxResidual = 0)

Solution: x=30 y=50

答えは当然というか、同じものが出た。でもアウトプットはpulpのほうが好きだなぁ。あっちならアウトプットから問題と制約も確認できるし。モデルの書き方はOpenOptというかFuncDesignerのほうが好き。なんか書いててモデルを構築してる感が出る。

実行時間としては若干こっちのほうがかかってるけど、体感的には誤差ですね。ライブラリ読み込みに時間がかかってるのかも。

real    0m0.598s
user    0m0.280s
sys     0m0.116s