Edited at

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

More than 1 year has passed since last update.

線形計画問題を解くフリーソフト 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)