サブロウ丸

Sabrou-mal サブロウ丸

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

pulp: 制約追加の高速化

環境

>>> import pulp
>>> pulp.__version__
'2.5.1'

本文

制約を大量に追加する場合 例えば;


\sum_{j=0}^{9999} x_j \leq f(i)  \quad ( \forall i = 0, ..., 999 )

を追加した場合、下記のコードだと実行時間 28.81 s かかります。(f(i)は実数を返す何かしらの関数)

prob = pulp.LpProblem()

# 変数の生成
x = [pulp.LpVariable(f'x{i}', 0, 1, 'Continuous') for i in range(10000)]
sum_x = pulp.lpSum(x)

for i in range(1000):
    prob += sum_x <= f(i)  # 制約の追加

ここで、

prob = pulp.LpProblem()

# 変数の生成
x = [pulp.LpVariable(f'x{i}', 0, 1, 'Continuous') for i in range(10000)]
sum_x = pulp.lpSum(x)

for i in range(1000):
-     prob += sum_x <= f(i)  # 制約の追加
+     sum_x.subInPlace(f(i))  # sum_x - f(i) ← sum_x
+     prob += pulp.LpConstraint(sum_x, pulp.const.LpConstraintLE)  # sum_x - i < 0
+     sum_x.addInPlace(f(i))  # sum_x ← sum_x - f(i)

に書き換えた場合、実行時間は 16.41 s になります。

なぜ速くなるか

下記のコードは全て GitHub - coin-or/pulp at v2.1 から抜粋.

class LpElement(object) の__sub__メソッドは以下のように定義されいて、

    def sub(self, other):
        return LpAffineExpression(self) - other

そしてclass LpAffineExpression(_DICT_TYPE)の__sub__メソッドは

    def sub(self, other):
        return self.copy().subInPlace(other)
    def copy(self):
        """Make a copy of self except the name which is reset"""
        # Will not copy the name
        return LpAffineExpression(self)

というようにオブジェクトの生成(copy)が一回挟まれます。


それに比べてclass LpAffineExpression(_DICT_TYPE)のsubInPlaceは オブジェクトの生成なしに直接self.constantを変更して、引き算を反映させるのでオブジェクトの生成が行われません。

基本的に新しいオブジェクト生成時にはメモリ確保から行われますが、このメモリの動的確保は通常の演算と比較してかなり時間がかかります。 そのためこのメモリの動的確保を省略できているので、速くなっているんですね。

    def subInPlace(self, other):
        if isinstance(other,int) and (other == 0):
            return self
        if other is None: return self
        if isinstance(other,LpElement):
            self.addterm(other, -1)
        elif isinstance(other,LpAffineExpression):
            self.constant -= other.constant
            for v,x in other.items():
                self.addterm(v, -x)
        elif isinstance(other,dict):
            for e in other.values():
                self.subInPlace(e)
        elif (isinstance(other,list)
              or isinstance(other, Iterable)):
            for e in other:
                self.subInPlace(e)
        else:
            self.constant -= other
        return self