概要
なんだかサイゼで効率良くカロリーを稼ぐ方法が計算ネタとして流行っているらしいので。
- サイゼリヤ1000円ガチャをつくってみた(Heroku + Flask + LINEbot)
- 「サイゼリヤで1000円あれば最大何kcal摂れるのか」を量子アニーリング計算(Wildqat)で解いてみた。
- 「サイゼリヤで1000円あれば最大何kcal摂れるのか」をSMTソルバー(Z3)で解いてみた。
量子アニーリング・SMTと来れば整数計画法も試してみたいところです。Pythonなら実装が簡単なので早速解いてみます。
なお、メニューセットは1行目の元記事の作者様のリポジトリからsaizeriya.db(SQLite)を参照することにします。
ソルバー選択・コーディング
Pythonで整数計画法と言えばPuLP。近頃もっと速くてPythonから叩きやすいソルバーとしてMIPCLというのが出たそうですが、ちゃちゃっと書きたいのでpipで入る前者を採用します。
問題データは普通に読み込んでDataFrameにします(扱いやすさを考慮)。
# 問題データを読み込む
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だとリスト記法で記述が楽になるのが良いですね。
# 解こうとする整数計画問題を作成
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つまでしか取らないものとします。
# 目的関数を設定
problem += pulp.lpDot(menu_df['calorie'], menu_df['order_flg'])
# 制約条件を設定
problem += pulp.lpDot(menu_df['price'], menu_df['order_flg']) <= LIMIT_PRICE
後は最適化するだけ。計算時間も測定することにします。
# 最適化を実施
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]
(良い意味で)枯れた技術だけあり、なんかもうパフォーマンスの暴力って感じですね。素晴らしきかな整数計画法。