線形計画問題を解くフリーソフト lp-solve 。
これをMacのターミナルで動かすまでの手順、そしてPythonから呼び出すまでの手順が何処にもまとまっていなかったので、記しておきます。
また、インストール出来たあとに使い方が分からなかったので、最後に簡単な事例でPythonのコードも記します。
環境
Mac OS X El Capitan 10.11.6
Python 2.7.12
※注意
homebrewでインストール方法を記載してましたが、
その方法では最新版がインストールされないため書き換えました。
lp_solveだけインストールできればいいよって方は、下記をお試しください。
$ brew tap homebrew/science
$ brew install lp_solve
lp_solve本体、Pythonインターフェイスのインストール
まず https://sourceforge.net/projects/lpsolve/files/lpsolve/ から、最新版のファイルをダウンロードします。必要なファイルは下記の2つです。
(2016/10/10時点最新：5.5.2.5)
lp_solve_5.5.2.5_source.tar.gz
lp_solve_5.5.2.5_Python_source.tar.gz
これらを解凍($tar xfvz)して、lp_solve_5.5.2.5_Python_source.tar.gz 内の /extra 以下を lp_solve_5.5.2.5_source.tar.gz 内の /lp_solve_5.5 内にコピーします。
ディレクトリ階層がこんな↓感じになったら、
lp_solve_5.5/
├ lp_solve
├ lpsolve55
├ extra
├ :
└ demo
lp_solve/ と lpsolve55/ 内で、
$ sh ccc.osx
とします。この時環境によっては大量にエラーが出ますが、必要なファイルは生成されます。
lp_solve/ → lpsolve55/ とsh ccc.osx をしたら、lpsolve55/bin が生成されていると思います。
生成されていれば /lpsolve55/bin/osx64/ 内にある liblpsolve55.a と liblpsolve55.dylib を /usr/loca/lib 内にコピーします。
最後に、 /lp_solve_5.5/extra/Python 内で setpy.pyを動かします。が、その前に、setpy.py内の以下の箇所を修正します。
:
:
windir = getenv('windir')
if windir == None:
WIN32 = 'NOWIN32'
LPSOLVE55 = '../../lpsolve55/bin/ux32' #→ lpsolve55/bin/osx64 に修正
else:
WIN32 = 'WIN32'
LPSOLVE55 = '../../lpsolve55/bin/win32'
setup (name = "lpsolve55",
version = "5.5.0.9",
description = "Linear Program Solver, Interface to lpsolve",
author = "Peter Notebaert",
:
:
保存したら、あとはターミナルで
$ python setpy.py install
すれば全てのインストールが完了です。
もしここで 'malloc.h' file not found エラーが出たら、指定の行(恐らく #include<malloc.h>)を #include<stdlib.h> に書き換えます。既にstdlib.hがincludeされていたら削除。
(参考：malloc.h on OS X)
正常にPythonから動くか確認してみましょう。
$python
Python 2.7.12 (default, Aug 3 2016, 23:22:34)
[GCC 4.2.1 Compatible Apple LLVM 7.3.0 (clang-703.0.31)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from lpsolve55 import *
>>> lpsolve()
lpsolve Python Interface version 5.5.0.9
using lpsolve version 5.5.2.5
Usage: ret = lpsolve('functionname', arg1, arg2, ...)
>>>
こんな感じになれば成功です。
Python内でのlp_splve記法
例えば次のような問題を解きたい場合、
目的関数
min -400x1 -300x2 + 100x3
制約
s.t. \qquad\qquad\qquad\qquad\qquad\\
60x1 +40x2 + 10x3 \le 3800\\
30x1 +20x2 -40 x3 \ge 1200\\
5 \ge x1 \ge -\infty \\
20 \ge x2, x3\\
int\ x1,x2,x3
次の様に制約式を追加していきます。
from lpsolve55 import *
# 0,3 →制約式が0行、変数が3このLPを作る
lp = lpsolve('make_lp',0,3)
# 目的関数追加 「min : -400x1 -300x2 +100x3」
lpsolve('set_obj_fn', lp, [-400, -300, 100] )
# 制約式追加 「60x1 +40x2 +10x3 =< 3800」, 「LE」 = 「<=」、 「GE」 = 「>=」、 「EQ」 = 「=」
lpsolve('add_constraint', lp, [60,40,10], LE, 3800)
# 30x1 +20x2 -40x3 => 1200
lpsolve('add_constraint', lp, [30,20,-40], GE, 1200)
# 変数の下限設定、 "Infinite"で無限を表現
lpsolve('set_lowbo',lp,1,-Infinite)
# 変数の上限設定、リストで同時に複数設定可
lpsolve('set_upbo',lp,[5,20,20])
# 整数制約、 0-1制約は "set_binary"
lpsolve('set_int'lp,[1,2,3])
# const.lpが生成され、定式化を出力
lpsolve('write_lp',lp,'const.lp')
# 問題を解く
lpsolve('solve',lp)
# 最適解の出力、変数に代入可。型はリスト
print lpsolve('get_variables',lp)
ざっと、よく使いそうなコマンドを並べてみました。その他のコマンドは lp_solve API reference で探し当ててください。僕も勉強中です。
今後
今現在気になっていることは、lp_solveの計算をある程度のところで止める機能がないか、ということです。
例えば「20sで終わらなければ、その時点での暫定解を出力する」みたいなことが出来たら良いななんて思いながら、探してます。
（追記:2016/10/7）有りました。
lpsolve('set_timeout',lp,TIME) # TIMEには秒数-1を設定。1分なら TIME = 59
で可能です。
参考文献
線形計画ソルバー
Python用のlpsolve driverをインストールする
lp_solve API reference
INSTALL LPSOLVE FOR PYTHON
lp_solveよりおすすめなライブラリ
Pythonにはより柔軟性が有る数理最適化のライブラリとしてPuLPというものがあります。
@SaitoTsutomu氏のこれらの記事が大変参考になります。
合わせて御覧ください。
初歩からの数理モデル
最適化におけるPython
数理最適化モデラー(PuLP)チートシート(Python)