Edited at

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

More than 3 years have passed since last update.


PuLP とは何か

線形計画問題を解く Python パッケージ。

https://code.google.com/p/pulp-or/

https://pythonhosted.org/PuLP/index.html

線形計画問題とは、目的関数と制約条件が1次式で表される最適化問題。

たとえば、


  • コストと利益が異なるいくつかの製品を、決まった数量作るときに、利益が最大になるような量の組み合わせを見つける。

  • パズルを解く

などが線形計画問題の一つ。

PyConJP 2014 で紹介されていたので使い方を調べてみると、

結構使いやすいのでまとめてみた。


インストール方法

sudo pip install pulp


手順


線形計画問題オブジェクトを作る

これが問題をすべて表現する。

コンストラクタには問題の名前と、目的関数を最小化するか最大化するかを選ぶ。

import pulp

problem = pulp.LpProblem('Problem Name', pulp.LpMinimize) # 最小化する場合
problem = pulp.LpProblem('Problem Name', pulp.LpMaximize) # 最大化する場合


変数オブジェクトを作る

線形計画で使う変数を作る。

作り方は2種類ある。大量の変数があるときは 2 を使うことが多そう。

(1) 1つずつ作る

pulp.LpVariable('name', 0, 1, 'Continuous') 

変数は前から順に、

1. 変数名

2. 変数の最小値

3. 変数の最大値

4. 変数の種類。連続値 (float) なら 'Continuous', 整数なら 'Integer', 2値変数なら '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'] こんな感じ。

これは今後の記事で使う予定。


目的関数を作る

変数を使って式を作り、数理計画問題オブジェクトに足す これがすごい。

たとえば、 ab の和を最大化したいときは

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


制約条件を作る

変数を使って比較を作り、数理計画問題オブジェクトに足す これもすごい。

たとえば、変数 ab の変数について、

1. a は 0以上

2. b は 0.1以上

3. ab の和は 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