サブロウ丸

主にプログラミングと数学

python pulp 変数和

pulpです。

変数の和を表現するときにsumよりもlpSumを使った方が高速にプログラムが動くという話です。

f:id:inarizuuuushi:20170813104509p:plain:w300
この簡単な最小化問題を例に。aは定数、bは実変数です。

import pulp
from random import randint

# A new Lp problem
prob = pulp.LpProblem('sample', pulp.LpMinimize)

n = 10000
a = [randint(0, 100) for i in range(n)] # 定数の定義
b = [pulp.LpVariable(name='b{}'.format(i), cat='Countinuous', lowBound=0) for i in range(n)] # 変数の定義

# objective
obj = sum([a[i]*b[i] for i in range(n)])
prob.setObjective(obj)

# constraint
prob += sum([b[i] for i in range(n)]) <= 3 # sum

# Solve the problem using the default solver
prob.solve()


python標準のsumを使って定数、変数の足し合わせが行えます。
このプログラムの実行時間は僕のpcで1m31.378sでした。

次に、

obj = sum([a[i]*b[i] for i in range(n)]) # これを
obj = pulp.lpSum([a[i]*b[i] for i in range(n)]) # こう


prob += sum([b[i] for i in range(n)]) <= 3 # これを
prob += pulp.lpSum([b[i] for i in range(n)]) <= 3 # こう


sumの部分をlpSumに書き換えて実行すると、実行時間は0m0.537sとなりました。

1分以上、実行時間が減りましたね。今までsumを使っていた自分の愚かさに、ガンジーもびっくりすることでしょう。(知らんけど)