2022-12-04

PuLP

PuLPとは

PuLPは、線形計画問題と混合整数線形計画問題のための人気のあるPythonライブラリです。PuLPは、数学的なプログラミング言語の高レベルインターフェースを提供し、Python固有の自然で表現力豊かな構文を使用して最適化問題を作成および解決することができます。

PuLPを使用すると、決定変数を作成し、目的関数を構築し、最適化問題の制約を定式化することができます。問題を定義した後、GLPK、COIN CLP/CBC、CPLEX、GUROBIなどのさまざまなソルバーを呼び出すためにPuLPを使用して、最適解を見つけることができます。

最適化の領域では、PuLPはしばしばSciPyやCVXPYなどのライブラリと比較されますが、PuLPは特に線形計画問題と混合整数線形計画問題に特化しており、さまざまなフリーソルバーや商用ソルバーとの相互作用能力により、柔軟性と広範な使用が可能です。

PuLPの主な特徴

PuLPライブラリは、以下の特徴があります。

高レベルインターフェース
PuLPは、最適化問題の構築に対してPythonらしい高レベルのインターフェースを提供します。これにより、Python開発者にとって直感的な選択肢となり、問題の定式化プロセスを簡素化することができます。PuLPは問題の基礎となる数学的な表現を抽象化し、ユーザーが論理的な定式化に集中することを可能にします。
ソルバーの柔軟性
PuLPは、COIN-ORのCBCやGLPKなどのオープンソースソルバーやGUROBIやCPLEXなどの商用ソルバーなど、さまざまなソルバーと連携することができます。これにより、ユーザーは特定のニーズや計算リソースに最適なソルバーを柔軟に選択することができます。
モデリングのパワー
PuLPを使用すると、複雑な目的関数や制約を定義することができ、現実の最適化シナリオの堅牢なモデリングが可能です。制約の追加、変更、削除が可能であり、モデルは非常に柔軟かつ適応性があります。

PuLPが解ける最適化問題の種類

PuLPはいくつかの最適化問題のクラスに対して強力なツールです。これには以下のものが含まれます。

線形計画問題 (LP)
整数計画問題 (IP)
混合整数線形計画問題 (MILP)
0-1整数計画問題

PuLPを用いたサプライチェーン最適化のケーススタディ

複数の工場からさまざまな店舗へ製品を配布する必要がある会社を考えてみます。各工場には最大生産能力があり、各店舗には特定の需要があります。また、各工場から各店舗への出荷にはコストがかかります。目的は、全ての店舗の需要を満たしながら、総配布コストを最小限に抑えることです。

このシナリオはクラシックな輸送問題であり、線形計画問題の一種であり、PuLPを使用して解決することができます。

問題の定式化

以下のように表記します。

工場を集合 $F={f_1, f_2, \ldots, f_n}$ とする
店舗を集合 $S={s_1, s_2, \ldots, s_m}$ とする
$c_{ij}$ を工場 $i$ から店舗 $j$ への1単位の製品の配送料とする
$x_{ij}$ を工場 $i$ から店舗 $j$ への出荷数量とする
$C_i$ を工場 $i$ の容量とする
$D_j$ を店舗 $j$ の需要とする

問題は次の線形プログラムとして定式化されます。

最小化:

Z = \sum_{i \in F} \sum_{j \in S} c_{ij}x_{ij} \\

制約条件:

\textrm{For each } i \in F: \sum_{j \in S} x_{ij} \leq C_i (\textrm{Capacity constraint}) \\ \textrm{For each } j \in S: \sum_{i \in F} x_{ij} \geq D_j (\textrm{Demand constraint}) \\ \textrm{For all } i,j: x_{ij} \geq 0 (\textrm{Non-negativity constraint})

データ

例えば、次のような工場と店舗があるとします。

python

capacity = {
    'Factory1': 1000,
    'Factory2': 4000
}

costs = {
    'Factory1': {'Store1': 2, 'Store2': 3},
    'Factory2': {'Store1': 4, 'Store2': 1}
}

demand = {
    'Store1': 500,
    'Store2': 4500
}

PuLPのコード

以下は、問題を定式化し解決するためのPuLPコードです。

python

from pulp import *

# Create the 'prob' variable to contain the problem data
prob = LpProblem("Supply_Chain_Optimization", LpMinimize)

# Decision variables
x = LpVariable.dicts("shipments", [(i,j) for i in capacity.keys() for j in demand.keys()], lowBound=0, cat='Continuous')

# Objective function
prob += lpSum([costs[i][j]*x[(i, j)] for i in capacity.keys() for j in demand.keys()])

# Constraints
for j in demand.keys():
    prob += lpSum([x[(i, j)] for i in capacity.keys()]) >= demand[j]

for i in capacity.keys():
    prob += lpSum([x[(i, j)] for j in demand.keys()]) <= capacity[i]

# Solve the problem
prob.solve()

結果

問題が解かれた後、各工場から各店舗へ出荷する単位数の最適解は次のコードで取得できます。

python

for v in prob.variables():
    print(v.name, "=", v.varValue)

shipments_('Factory1',_'Store1') = 500.0
shipments_('Factory1',_'Store2') = 500.0
shipments_('Factory2',_'Store1') = 0.0
shipments_('Factory2',_'Store2') = 4000.0

このコードは最適解、つまり各工場から各店舗への出荷単位数を表示し、最適な総コストはprob.objective.value()で取得できます。

python

print("Total Cost of Transportation =", value(prob.objective))

Total Cost of Transportation = 6500.0

上記のコードは、全ての需要を満たすために各工場から各店舗へ出荷するための最小の総コストを表示します。

PuLP

PuLPとは

PuLPの主な特徴

PuLPが解ける最適化問題の種類

PuLPを用いたサプライチェーン最適化のケーススタディ

問題の定式化

データ

PuLPのコード

結果

参考

最適化問題

Python-MIP

Ryusei Kakujo