PuLPで変数を沢山作るときはLpVariable.dictsを使おう

最適化をやっていると、変数を一度に沢山作る機会があります。pythonで最適化をやる際におそらく一番使われるPuLPで、その書き方を強調して書いてあるものが少なかったので、ご参考になればと思い書いときます。

3行サマリ

• 変数はpulp.LpVariablle.dictsで作成する
• 式の表現はlpSumを使う

がおすすめです。

LpVariable.dictsを使うべき理由

書き方がいくつかあるなかで、なぜLpvariable.dictsが良いのかというと、、、

理由１：リストの何番目とか分からなくなるので

他の代表的な書き方に「for文や内包表記で変数のリストを作成する」というものがあると思います。

でも、商品Aにだけこの制約を加えたい、だとか地点Bから地点Cに行くことだけは避けたい、みたいな制約を入れたいときってありますよね。リストで作成していると、その商品や地点ってリストの何番目？となるわけです。

一説によると人間が短期記憶できる数は7個程度とも言われていますし¹、インドのPuri族には数を表す概念は１，２，沢山のみだそうです²。つまり数という概念は人間にとって分かりやすいものではないというわけです。私も5を超えるとだいたい途中で分からなくなって2~3回数え直します

ということで、リストの何番目かを考えるのはいまの人類には高度すぎるため、なるべく苦手なことに脳を使わないですむように辞書を用いるのが良いと思います。

理由２：公式のexampleもそれを使っているので

Docsにある例もそうですし、githubにおいてある例もそうなっています。

自分もそこまで沢山知っているわけではないですが、最適化の文脈だと辞書で作るのがひとつのスタンダードであると思います。例えばgurobiのexampleもそうでした³。長いものには巻かれときましょう。

例

ということで、じゃあ具体的にこう書くのがいいだろう、と私が考えているものを例を用いて見ていきます。

標準的なナップサック問題を解きます。題材は駄菓子にしましょう。遠足でよくある、300円までで一番魅力的な駄菓子パーティーを組む問題です。数式で書くと

\begin{align}
\max ~ & \sum_{i\in I}Value_i \cdot x_i \\
s.t. ~ & \sum_{i\in I}Price_i \cdot x_i <= 300 \\
& x_i \in \{0,1\}
\end{align}

です。$x_i$はおかし$i$を買うならば1、買わないならば0をとる変数とします。金額の合計が300円を超えないように、価値が最大になるように買う商品を選ぶわけです。同じおかしを複数個買うようなパーティーが最強であるわけがないので、$x_i$は整数でなくてBinaryにしています。これを以降ではKnapSnack問題と呼びます。

データの取得

価格が分からないと問題が解けないので、そのデータを取得します。みんな大好き、やおきんさんのオンラインショップからスクレイピングします⁴。ここは記事の本題とは関係ないので、お急ぎの型は最適化パートまで飛んでも大丈夫です。

import requests
from bs4 import BeautifulSoup
import numpy as np
import pandas as pd

df = pd.DataFrame()
for i in range(19):
    url = f'https://dagasiya.com/shop/shopbrand.html?page={i}&search=&sort=&money1=&money2=500&prize1=&company1=&content1=&originalcode1=&category=&subcategory='
    res = requests.get(url)
    soup = BeautifulSoup(res.text, "html.parser")
    name = soup.find_all('p', class_='itemName')
    price = soup.find_all('p', class_='itemPrice')
    df_page = pd.DataFrame({
        'Name': [i.text for i in name],
        'Price': [i.text for i in price]
    })
    df = df.append(df_page)


df = df.drop_duplicates('Name')
df['Value'] = np.abs(np.random.randn(len(df)))
df['Price'] = df['Price'].str[:-1].astype(int)

スクレイピングは本記事の本題ではないので、さっとさらうだけにします⁵。

• 高すぎる駄菓子はロマンがないので、500円以下のものに絞ります
  • urlのmoney2=500のところが該当します
• requestsを用いてhtmlを取得します
• BeautifulSoupを用いてパース（文字列を分かりやすい形に整理）します
• 商品名と価格に対応するcssのclassをもつ要素をすべて取得します
• 取得した結果を、pandasのDataFrameに格納します
• 以上を検索結果ページ数(19ページ)分繰り返します

さらに、最適化の都合で以下の操作を加えます。

• 同じ商品名のものがあるとどっちがどっちか分からなくなるので、商品名が重複しているものは片方省きます
• 「一番魅力的なパーティー」の定義は非常に難しい問題ですが、ここでは適当に乱数で個々の商品の価値をつけています
• 価格が「450円」のような形で取得されたので、円を削除してint型に変形します

できあがったDataFrameがこちらです。

さて、困ったことに、20個入りなどの単位でしか売ってません。まあそりゃオンラインで駄菓子1個単位で打ってたら商売成り立たないか。。

まあ個数当たりの金額にしたりするのは面倒なので、無視してこのままいきましょう。

最適化の実行

price = df.set_index('Name')['Price'].to_dict()
value = df.set_index('Name')['Value'].to_dict()

まず、最適化に用いる定数を辞書として用意します。別にpandasのまま処理してもいいのだけど、公式のexampleと対応するように辞書にしています。

ここではkeyが商品名で、valueがそれぞれ価格や価値であるような辞書ができます。valueが被っていてイケてないですね。。すみません

では本題のPuLPの部分です。

# 問題の作成
prob = pulp.LpProblem(name='KnapSnack', sense=-1)
# 変数の作成
x = pulp.LpVariable.dicts('x', df['Name'], cat='Binary')
# 目的関数の追加
prob += pulp.lpSum([x[i] * value[i] for i in x.keys()])
# 制約の追加
prob += pulp.lpSum([x[i] * price[i] for i in x.keys()]) <= 30 * 300

# 求解
sol = prob.solve()
# 解けているかを確認
print(pulp.LpStatus[sol])          # Optimal
# 最適解を確認
print(pulp.value(prob.objective))  # 61.21364708355906

1. 問題の作成
2. 変数の作成：'x'が変数の名前、次に辞書のkeyに対応するもの、最後にBinary変数を指定しています。これで、keyが商品名でvalueがPuLPの変数である辞書が作成されます
3. 目的関数の追加：基本的にはlpSumを使うことになるでしょう。リスト内包表記で足し上げる要素を羅列するのをよく見ます
4. 制約の追加：先ほど見たように単位がバグってたので、一クラス分（30人×300円）を買う問題に変更していますw
5. 求解

ということで、シンプルに記述できました。以下で変数の作り方について補足します。

変数の作成

LpVariable.dicts(name, indexs, lowBound=None, upBound=None, cat='Continuous', indexStart=[])

引数は、nameが変数名です。indexsが辞書のkeyになるもので、文字列のリストを渡します。
他は色んなところに書いてあるのと同じなので略します。

結果

そういえば結果です。こいつらが最強のおかしパーティーです。

	商品名	価格	ポイント
13	うまい棒鉛筆3種（HB・B・2B）各3本セット ＋ 特典	475	1.958077
19	つけつけペロスティックチョコ　6入り	311	0.360806
2	新サワーコーラグミ　６０入り	518	1.042587
18	ペンシルカルパス　20入り	518	0.017585
23	ガブリチュウ・グレープ　20入り	518	0.144169
3	オレンジマーブルガム　24入り	311	0.260376
4	ドラえもんマーブルガム　24入り	311	0.464725
12	もちっときなこ餅　20入り	518	0.310539
20	カジリッチョ　サイダー味　20入り	518	0.962775
12	フルーツモンスターレインボー味　12入り	518	0.909126
5	BR　出前寿司セット　1個	385	1.410559
9	BR　富士山と神社　1個	385	0.937255
18	BR　スポーツセット　1個	385	0.180035
0	BR　お寿司　1個	385	1.340095
1	BR　お料理　1個	385	0.490019
12	こんぺいとう　20個入	518	0.438453
14	塩吉原羊かん　12入り	259	1.477365
16	ミニしみチョココーン　ミルクチョコ　10入り	432	1.221638
8	ましゅろー　30入り	259	1.519683
21	もちもちきなこ　12入り	518	0.700150
8	変わり味　ギョギョギョガム　20入り	518	0.291298
1	ゾンBのもとガム　18入り	467	1.365611
2	ドラQラのもとガム　18入り	467	0.864054
18	うまい棒お箸　小　とんかつソース　1膳	317	0.239067
19	うまい棒お箸　大　とんかつソース　1膳	317	0.755195
11	うまい棒フォーク　タコヤキ　1本	317	0.292592
14	うまい棒フォーク　チーズ　1本	317	0.891636
20	フライドポテト　30入り	518	1.119859
18	うまい棒プチマスコット・メンタイ　1個	288	1.381736
19	うまい棒プチマスコット・ソース　1個	288	0.615968
8	うまい棒やさいサラダ味　30本	259	0.981209
10	うまい棒とんかつソース味　30本	259	1.491541

まあ結局価値のところを乱数で出しているので大して意味のある結果にはなっていませんが、やっぱりうまい棒は強いですね。うまい棒最強。あとお寿司がしれっと混ざっているのは笑いました。

おまけ

実は他にもこんなのがあるけど、あまり推奨されてないんじゃないかな、というものです。

自作で変数のリストを作る

散々本記事で書いている通りです。や、手元でサッと作るだけとか、規模が大きくないとかなら問題ないとは思います。

LpVariable.matrix

LpVariable.dictsと同じノリで変数の行列を作ってくれるメソッドがあります。しかし、辞書のほうが良いということで機能としてはあるもののドキュメントには載っていません⁶。

lpDot

lpSumと同じノリで内積（$\sum_i x_i p_i$みたいな）を計算してくれる関数が存在します。しかしこれも辞書とは相性が悪いので（リストとかだとi番目同士を掛けるけど、辞書に対しては...）、こちらもドキュメントに載っていません。

---

1. まあ色々な条件のもとでの実験の結果で、適切な解釈はだいぶ違うのでしょうが。https://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A7%E3%83%BC%E3%82%B8%E3%83%BB%E3%83%9F%E3%83%A9%E3%83%BC_(%E5%BF%83%E7%90%86%E5%AD%A6%E8%80%85) ↩

2. ちゃちゃっと調べただけなので少し古い論文ですが、こちらなどが参考です。https://opera.repo.nii.ac.jp/?action=repository_action_common_download&item_id=6500&item_no=1&attribute_id=19&file_no=1 ↩

3. https://www.gurobi.com/documentation/9.1/examples/diet_py.html ↩

4. こちらのページです：https://dagasiya.com/shop/shopbrand.html?page=1&search=&sort=&money1=&money2=500&prize1=&company1=&content1=&originalcode1=&category=&subcategory= ↩

5. ちなみに余談ですが、やおきんさんのオンラインショップはスクレイピングするのにちょうどいい題材だと感じました（複雑すぎることもないし、きれいなコードで作られている気がしました）。スクレイピング初心者におすすめです。 ↩

6. ドキュメントにないのはそれはそれで分かりにくいので、載せたうえで非推奨とかって書いてほしいものですけどね。 ↩