PuLP とは何か
線形計画問題を解く Python パッケージ。
https://code.google.com/p/pulp-or/
https://pythonhosted.org/PuLP/index.html
線形計画問題とは、目的関数と制約条件が１次式で表される最適化問題。
たとえば、
- コストと利益が異なるいくつかの製品を、決まった数量作るときに、利益が最大になるような量の組み合わせを見つける。
- パズルを解く
などが線形計画問題の一つ。
PyConJP 2014 で紹介されていたので使い方を調べてみると、
結構使いやすいのでまとめてみた。
インストール方法
sudo pip install pulp
手順
線形計画問題オブジェクトを作る
これが問題をすべて表現する。
コンストラクタには問題の名前と、目的関数を最小化するか最大化するかを選ぶ。
import pulp
problem = pulp.LpProblem('Problem Name', pulp.LpMinimize) # 最小化する場合
problem = pulp.LpProblem('Problem Name', pulp.LpMaximize) # 最大化する場合
変数オブジェクトを作る
線形計画で使う変数を作る。
作り方は２種類ある。大量の変数があるときは 2 を使うことが多そう。
(1) 1つずつ作る
pulp.LpVariable('name', 0, 1, 'Continuous')
変数は前から順に、
1. 変数名
2. 変数の最小値
3. 変数の最大値
4. 変数の種類。連続値 (float) なら 'Continuous', 整数なら 'Integer', ２値変数なら 'Binary'
このコードで、変数名 name で、0から1の連続値をとる変数を生成できる。
(2) リストを渡してまとめて作る
var = pulp.LpVariable.dicts('VAR', ([1,2,3], ['a', 'b']), 0, 1, 'Continuous')
変数は前から順に、
1. 変数名の prefix
2. 変数名の postfix のリストのタプル
3. 変数の最小値
4. 変数の最大値
5. 変数の種類
3-5 は前と同じ。
このコードを実行すると、最小値 0, 最大値 1, で連続値をとる
変数群 VAR_1_a, VAR_1_b, VAR_2_a, ... を持つディクショナリが手に入る。
アクセス方法は var[1]['a'] こんな感じ。
これは今後の記事で使う予定。
目的関数を作る
変数を使って式を作り、数理計画問題オブジェクトに足す これがすごい。
たとえば、 a と b の和を最小化したいときは
import pulp
problem = pulp.LpProblem('test', pulp.LpMinimize)
a = pulp.LpVariable('a', 0, 1)
b = pulp.LpVariable('b', 0, 1)
problem += a + b
この状態で problem を print すると、問題が表示される。
test:
MINIMIZE
1*a + 1*b + 0
VARIABLES
a <= 1 Continuous
b <= 1 Continuous
制約条件を作る
変数を使って比較を作り、数理計画問題オブジェクトに足す これもすごい。
たとえば、変数 a と b の変数について、
1. a は 0以上
2. b は 0.1以上
3. a と b の和は 0.5
という制約を作りたいときは、
problem += a >= 0
problem += b >= 0.1
problem += a + b == 0.5
反不等号 (<=, =>) しか使えなかった。
解く
problem.solve()
これだけ。
制約条件によっては解けない場合があるので、結果を知りたいときは、
status = problem.solve()
print pulp.LpStatus[status]
で Optimal が出れば OK
結果を取り出す。
problem に追加した変数の value メソッドを呼ぶと、値が手に入る。
まとめると
import pulp
problem = pulp.LpProblem('sample', pulp.LpMinimize)
a = pulp.LpVariable('a', 0, 1)
b = pulp.LpVariable('b', 0, 1)
problem += a + b
problem += a >= 0
problem += b >= 0.1
problem += a + b == 0.5
status = problem.solve()
print "Status", pulp.LpStatus[status]
print problem
print "Result"
print "a", a.value()
print "b", b.value()
結果は、
Status Optimal
sample:
MINIMIZE
1*a + 1*b + 0
SUBJECT TO
_C1: a >= 0
_C2: b >= 0.1
_C3: a + b = 0.5
VARIABLES
a <= 1 Continuous
b <= 1 Continuous
Result
a 0.4
b 0.1