最適化をやっていると、変数を一度に沢山作る機会があります。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 | 1.0 |
| 19 | つけつけペロスティックチョコ　6入り | 311 | 0.360806 | 1.0 |
| 2 | 新サワーコーラグミ　６０入り | 518 | 1.042587 | 1.0 |
| 18 | ペンシルカルパス　20入り | 518 | 0.017585 | 1.0 |
| 23 | ガブリチュウ・グレープ　20入り | 518 | 0.144169 | 1.0 |
| 3 | オレンジマーブルガム　24入り | 311 | 0.260376 | 1.0 |
| 4 | ドラえもんマーブルガム　24入り | 311 | 0.464725 | 1.0 |
| 12 | もちっときなこ餅　20入り | 518 | 0.310539 | 1.0 |
| 20 | カジリッチョ　サイダー味　20入り | 518 | 0.962775 | 1.0 |
| 12 | フルーツモンスターレインボー味　12入り | 518 | 0.909126 | 1.0 |
| 5 | BR　出前寿司セット　1個 | 385 | 1.410559 | 1.0 |
| 9 | BR　富士山と神社　1個 | 385 | 0.937255 | 1.0 |
| 18 | BR　スポーツセット　1個 | 385 | 0.180035 | 1.0 |
| 0 | BR　お寿司　1個 | 385 | 1.340095 | 1.0 |
| 1 | BR　お料理　1個 | 385 | 0.490019 | 1.0 |
| 12 | こんぺいとう　20個入 | 518 | 0.438453 | 1.0 |
| 14 | 塩吉原羊かん　12入り | 259 | 1.477365 | 1.0 |
| 16 | ミニしみチョココーン　ミルクチョコ　10入り | 432 | 1.221638 | 1.0 |
| 8 | ましゅろー　30入り | 259 | 1.519683 | 1.0 |
| 21 | もちもちきなこ　12入り | 518 | 0.700150 | 1.0 |
| 8 | 変わり味　ギョギョギョガム　20入り | 518 | 0.291298 | 1.0 |
| 1 | ゾンBのもとガム　18入り | 467 | 1.365611 | 1.0 |
| 2 | ドラQラのもとガム　18入り | 467 | 0.864054 | 1.0 |
| 18 | うまい棒お箸　小　とんかつソース　1膳 | 317 | 0.239067 | 1.0 |
| 19 | うまい棒お箸　大　とんかつソース　1膳 | 317 | 0.755195 | 1.0 |
| 11 | うまい棒フォーク　タコヤキ　1本 | 317 | 0.292592 | 1.0 |
| 14 | うまい棒フォーク　チーズ　1本 | 317 | 0.891636 | 1.0 |
| 20 | フライドポテト　30入り | 518 | 1.119859 | 1.0 |
| 18 | うまい棒プチマスコット・メンタイ　1個 | 288 | 1.381736 | 1.0 |
| 19 | うまい棒プチマスコット・ソース　1個 | 288 | 0.615968 | 1.0 |
| 8 | うまい棒やさいサラダ味　30本 | 259 | 0.981209 | 1.0 |
| 10 | うまい棒とんかつソース味　30本 | 259 | 1.491541 | 1.0 |

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

おまけ

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

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

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

LpVariable.matrix

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

lpDot

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