Python
MacOSX
lp_solve
python2.7

Mac OSXにlp_solveをインストールして、pythonで呼び出す。

線形計画問題を解くフリーソフト lp-solve 。
これをMacのターミナルで動かすまでの手順、そしてPythonから呼び出すまでの手順が何処にもまとまっていなかったので、記しておきます。
また、インストール出来たあとに使い方が分からなかったので、最後に簡単な事例でPythonのコードも記します。

環境

Mac OS X EI Captain 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内の以下の箇所を修正します。

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)