1. YSRKEN

    Posted

    YSRKEN
Changes in title
+サイゼ最適化問題 vs 整数計画ソルバー by Python
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,121 @@
+# 概要
+
+ なんだか**サイゼで効率良くカロリーを稼ぐ方法**が計算ネタとして流行っているらしいので。
+
+- [サイゼリヤ1000円ガチャをつくってみた(Heroku + Flask + LINEbot)](https://qiita.com/marusho_summers/items/a2d3681fac863734ec8a)
+- [「サイゼリヤで1000円あれば最大何kcal摂れるのか」を量子アニーリング計算(Wildqat)で解いてみた。](https://qiita.com/hodaka0714/items/cf44b4ece992a39b5be4)
+- [「サイゼリヤで1000円あれば最大何kcal摂れるのか」をSMTソルバー(Z3)で解いてみた。](https://qiita.com/tanakh/items/a1fb13f78e0576415de3)
+
+ 量子アニーリング・SMTと来れば整数計画法も試してみたいところです。Pythonなら実装が簡単なので早速解いてみます。
+ なお、メニューセットは[1行目の元記事の作者様のリポジトリ](https://github.com/marushosummers/Saizeriya_1000yen)から`saizeriya.db`(SQLite)を参照することにします。
+
+# ソルバー選択・コーディング
+
+Pythonで整数計画法と言えば[PuLP](https://pythonhosted.org/PuLP/)。近頃もっと速くてPythonから叩きやすいソルバーとして[MIPCL](http://mipcl-cpp.appspot.com)というのが出たそうですが、ちゃちゃっと書きたいので`pip`で入る前者を採用します。
+
+問題データは普通に読み込んで`DataFrame`にします(扱いやすさを考慮)。
+
+```py
+# 問題データを読み込む
+menu_list = {'name': [], 'price': [], 'calorie': []}
+with closing(sqlite3.connect('saizeriya.db')) as conn:
+ c = conn.cursor()
+ for row in c.execute('SELECT name, price, calorie FROM menu'):
+ menu_list['name'].append(row[0])
+ menu_list['price'].append(row[1])
+ menu_list['calorie'].append(row[2])
+menu_df = pandas.DataFrame.from_dict(menu_list)
+```
+
+次に問題、問題で使用する変数を宣言します。Pythonだとリスト記法で記述が楽になるのが良いですね。
+
+```py
+# 解こうとする整数計画問題を作成
+problem = pulp.LpProblem("Saizeriya", pulp.LpMaximize)
+
+# 問題で使用する変数を作成
+menu_df['order_flg'] = [pulp.LpVariable(f'x{i}', cat=pulp.LpBinary) for i in menu_df.index]
+```
+
+後は目的関数と制約条件ですが、PuLPの場合、内積を求めるのにやたら都合がいい`pulp.lpDot`という関数があるのでそちらを利用します。変数宣言からもお察しの通り、各メニューは最大1つまでしか取らないものとします。
+
+```py
+# 目的関数を設定
+problem += pulp.lpDot(menu_df['calorie'], menu_df['order_flg'])
+
+# 制約条件を設定
+problem += pulp.lpDot(menu_df['price'], menu_df['order_flg']) <= LIMIT_PRICE
+```
+
+後は最適化するだけ。計算時間も測定することにします。
+
+```py
+# 最適化を実施
+start_time = time.time()
+result_status = problem.solve()
+elapsed_time = time.time() - start_time
+
+# 結果を表示
+print(f'最適化結果({int(pulp.value(problem.objective))}カロリー):')
+menu_df['result'] = menu_df['order_flg'].apply(lambda x: pulp.value(x))
+menu_df = menu_df.query('result > 0.0')
+print(menu_df[['name', 'price', 'calorie']])
+
+print(f'計算時間:{elapsed_time}[s]')
+```
+
+# 計算結果
+
+```
+【実行環境】
+OS:Windows 10 Pro
+CPU:Intel Core i7-4790K
+メインメモリ:DDR3、16GB
+Python:3.7.1
+PuLP:1.6.10
+
+【予算1000円の場合】
+最適化結果(1940カロリー):
+ name price calorie
+24 ポテトのグリル 199 366
+72 アーリオ・オーリオ(Wサイズ) 574 1120
+100 ラージライス 219 454
+計算時間:0.029977798461914062[s]
+
+【予算10000円の場合】
+最適化結果(17048カロリー):
+ name price calorie
+24 ポテトのグリル 199 366
+27 フォッカチオ 119 214
+28 プチフォッカ 139 214
+52 パンチェッタのピザ 399 646
+53 野菜ときのこのピザ 399 610
+59 アラビアータ 399 591
+62 アーリオ・オーリオ 299 560
+63 キャベツのペペロンチーノ 399 686
+64 タラコソースシシリー風 399 605
+66 パルマ風スパゲッティ 399 700
+68 カルボナーラ 499 865
+70 アラビアータ(Wサイズ) 770 1182
+72 アーリオ・オーリオ(Wサイズ) 574 1120
+73 キャベツのペペロンチーノ(Wサイズ) 770 1372
+74 タラコソースシシリー風(Wサイズ) 770 1210
+75 パルマ風スパゲッティ(Wサイズ) 770 1400
+77 カルボナーラ(Wサイズ) 976 1730
+80 ミラノ風ドリア 299 542
+81 半熟卵のミラノ風ドリア 368 632
+82 セットプチフォッカ付きミラノ風ドリア 378 649
+99 ライス 169 303
+100 ラージライス 219 454
+101 スモールライス 119 151
+104 シナモンフォッカチオ 169 246
+計算時間:0.10295629501342773[s]
+```
+
+(良い意味で)枯れた技術だけあり、なんかもう**パフォーマンスの暴力**って感じですね。素晴らしきかな整数計画法。
+
+# 参考記事
+
+- [Python+PuLPによるタダで仕事に使える数理最適化](https://qiita.com/samuelladoco/items/703bf78ea66e8369c455)
+- [最適化におけるPython](https://qiita.com/SaitoTsutomu/items/070ca9cb37c6b2b492f0)
+- [ついに使い物になるフリーの数理最適化ソルバーが登場? MIPCL](https://qiita.com/keisukesato-ac/items/0049f33e10aab9d87734)