PuLP による線型計画問題の解き方ことはじめ

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