はじめに
こんにちは。T.H.です。
今回は、数理最適化問題を解くためのPythonライブラリであるPuLPについて数理最適化そのものにも触れつつ記載します。
経緯
数理最適化の実装について調べ始めていたころ、PuLPというモデラーが真っ先に引っ掛かり、調査しました。
結局機能不足で当時のプロジェクトには使用できないことが判明したため、この記事で供養しておこうという意図です。
PuLPとは
Pythonのライブラリで数理最適化問題を解くために用いるモデラーです。
ここでいうモデラーとは、数理最適化の問題や制約条件をコード上のモデルに落とし込むためのライブラリのことを言います。
実際に数理最適化を解くためのソルバーについては幾つか選択できますが、お試しで使う分にはソルバーについては特に意識しなくても構いません。
デフォルトのCBc(COIN-OR Branch and cut)でよいでしょう。
pipでインストールできます。
pip install pulp数理最適化問題とは
※前提として数学的に正しいか、よりも分かりやすさを重視しています。
Wikipediaの数理最適化の項目によると
数学の計算機科学やオペレーションズリサーチの分野における数理最適化（すうりさいてきか、英: mathematical optimization）とは、（ある条件に関して）最もよい元を、利用可能な集合から選択することをいう。
とあります。
非常にざっくり言うと、いろんな選択肢があるものの中から最もいい感じの答えを求める問題、ということになります。
問題のパターンによって名前がついていたりします。
- いくつかの都市を最も効率よく回るパターンを見つける（巡回セールスマン問題）
- 重量制限のある袋に最も効率よく荷物を詰め込むパターンを見つける（ナップサック問題）
- 看護師などの出勤シフトで最も効率よい、あるいは負荷の少ないパターンを見つける（ナーススケジューリング問題）
制約条件と目的関数
答えを求めるに当たっての制約を「制約条件」、
良い答えを求める指標を「目的関数」といいます。
例として、
重量制限のある袋に最も効率よく荷物を詰め込むパターンを見つける（ナップサック問題）
の場合は、重量制限が「制約条件」、詰められた荷物の数や価値が「目的関数」となります。
実例
PuLPを使って実際にナップサック問題を解いてみましょう。
単純なナップサック問題を解くコードは下記になります。
import pulp
n = 5 # 荷物の数
w_capacity = 200 # 重量の最大値
weights = [103, 87, 32, 67, 49] # 各荷物の重量
values = [76, 25, 52, 80, 26] # 各荷物の価値
# 問題を定義。pulp.LpMaximizeで最大化を指定
prob = pulp.LpProblem('knapsack', sense=pulp.LpMaximize)
# 変数の定義。荷物として入れているかを0,1のbinaryで表現
vars = [pulp.LpVariable('{}'.format(x), cat='Binary', lowBound=0, upBound=1) for x in range(n)]
prob += pulp.lpDot(values, vars) # values(係数),vars(変数)の内積を目的関数として登録
prob += pulp.lpDot(weights, vars) <= w_capacity # 重量の最大値を制約条件として追加
# 実行
status = prob.solve()
print([x.value() for x in vars])意外と短いですね。
では順番に見ていきましょう。
n = 5 # 荷物の数
w_capacity = 200 # 重量の最大値
weights = [103, 87, 32, 67, 49] # 各荷物の重量
values = [76, 25, 52, 80, 26] # 各荷物の価値データを定義しています。
5個の荷物があって、それぞれに重量と価値が定義されている。という状態です。
# 問題を定義。pulp.LpMaximizeで最大化を指定
prob = pulp.LpProblem('knapsack', sense=pulp.LpMaximize)pulp.LpProblem()で問題を定義します。
第1引数は問題の名前、第2引数のsense=で最大化、最小化のどちらかを指定します。
pulp.LpMaximizeで最大化、pulp.LpMinimizeで最小化です。
# 変数の定義。荷物として入れているかを0,1のbinaryで表現
vars = [pulp.LpVariable('{}'.format(x), cat='Binary', lowBound=0, upBound=1) for x in range(n)]変数を定義します。ここでの変数とは、最適化を実行するうえで可変となる値です。
今回は、各荷物が入っている状態を1、入っていない状態を0と考えます。
pulp.LpVariable('{}'.format(x), cat='Binary', lowBound=0, upBound=1)
で荷物一つ分の変数を定義しています。それを内包表記で荷物の個数分用意している、という構造になります。
LpVariableの第1引数が名前、cat=で変数の種類を定義します。
ここではcat='Binary'のため、0か1のみを取りうるということになります。
| cat | 種類 |
|---|---|
| Continuous | 実数 |
| Integer | 整数 |
| Binary | 0 or 1 |
引数説明の続きです。lowBound=で変数の下限値、upBound=で変数の上限値を定義します。
ここではcat='Binary'を指定しているため、定義はしていますが意味はありません。省略した場合は無限になります。
通常はcat='Integer'or'Continuous'の場合に使用します。
prob += pulp.lpDot(values, vars) # values(係数),vars(変数)の内積を目的関数として登録
prob += pulp.lpDot(weights, vars) <= w_capacity # 重量の最大値を制約条件として追加prob +=で目的関数と制約条件を登録します。
prob += pulp.lpDot(values, vars) # values(係数),vars(変数)の内積を目的関数として登録で目的関数を登録しています。
pulp.lpDot(values, vars)はvaluesとvarsの内積を計算します。内積は高校数学の範囲ですね。定義を聞いただけですと難しい気がしますが、ここでやっていることは単純です。
それぞれの荷物に対してvalues と varsの掛け算をしているだけですね。
| values | vars | 結果 |
|---|---|---|
| 76 | 0 | 0 |
| 25 | 1 | 25 |
| 52 | 0 | 0 |
| 80 | 1 | 80 |
| 26 | 0 | 0 |
目的関数ですので、「結果」の値の合計が最大となるvarの組み合わせを探す、ということになります。
prob += pulp.lpDot(weights, vars) <= w_capacity # 重量の最大値を制約条件として追加こちらは制約条件です。<= w_capacityで、重量の合計値が設定値を超えない、という条件を付与しています。
制約条件で使用可能な条件式は <=,==,>= のみです。<>を単独では使用できません。
また、目的関数の登録と制約条件の登録方法は非常に似通っていますが、両者の違いは条件式の有無です。条件式があれば制約条件、無ければ目的関数となります。
# 実行
status = prob.solve()
print([x.value() for x in vars])で実行と結果の表示をします。変数の結果はなぜか表示されないので自力で表示させています。
実際に実行してみましょう。
～～～省略～～～
Result - Optimal solution found
Objective value: 158.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.00
Time (Wallclock seconds): 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.00
[0.0, 0.0, 1.0, 1.0, 1.0]ログのようなものが出て最後に結果が表示されました。
Objective value: 158.00000000が目的関数の結果、
[0.0, 0.0, 1.0, 1.0, 1.0]がその時の変数です。後ろ3つの荷物を入れたときに価値が最大化する、ということが見えます。
少し応用
vars = [pulp.LpVariable('{}'.format(x), cat='Binary', lowBound=0, upBound=1) for x in range(n)]を修正し、
vars = [pulp.LpVariable('{}'.format(x), cat='Integer', lowBound=0, upBound=2) for x in range(n)]としてみます。これで問題の意味合いが変わり、
「同じ荷物を最大2個で入れることが出来る」ということになります。
では、実行してみましょう
Result - Optimal solution found
Objective value: 264.00000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.00
Time (Wallclock seconds): 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.00
[0.0, 0.0, 2.0, 2.0, 0.0]3番目と4番目の荷物を2個ずつ入れるのがベスト、という結果になりました。
PuLPの制限事項
PuLPでは扱うことができる問題に制限があります。
実運用で使用できなかった原因です。
- 目的関数と制約条件が1次式である
- 中間状態を制約条件として反映できない
1.は1次式ですので 固定値×変数Xは可能でも、変数X×変数Yが不可能です。
2.は互いの項目同士で影響しあう制約条件が書けないため、こちらも大きな制約となります。
結論としては、おそらくかなり単純な問題以外に適用するのは難しいかと思われます。
Python-MIPやOR-Toolsなど、他の最適化用無料ライブラリがあるため、まずそちらから検討され方が良いかもしれません。
最後に
私自身もPuLPを使いこなしているわけではなく、調べた範囲の内容にとどまりますが、少しでも参考になれば幸いです。
数理最適化は大学数学の領分のため深堀すると大変なのですが、今回のナップサック問題のような「組合せ最適化問題」は仕組みそのものは単純なので調べてみると面白いかと思います。
お読みいただきありがとうございました。
番外:数理最適化はAIと関連はありますか？
今のディープラーニングをベースとしたAIブームのはるか昔から存在していました。
アルゴリズムとしては数十年前からある手法で、現在の流行りの技術とは別物（ルーツではあります）です。
古いですが、研究されてきたアルゴリズムそのものは強力で、
ナーススケジューリング問題のように限定された状況においては現実の問題を十分に解決することが出来ます。
参考
https://qiita.com/SaitoTsutomu/items/070ca9cb37c6b2b492f0
https://qiita.com/maskot1977/items/41f5e72309b5274f54a0
https://docs.pyq.jp/python/math_opt/pulp.html
http://www.nct9.ne.jp/m_hiroi/light/pulp01.html