概要

　なんだかサイゼで効率良くカロリーを稼ぐ方法が計算ネタとして流行っているらしいので。

　量子アニーリング・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]

(良い意味で)枯れた技術だけあり、なんかもうパフォーマンスの暴力って感じですね。素晴らしきかな整数計画法。

「サイゼリヤで1000円あれば最大何kcal摂れるのか」を整数計画法ソルバー(PuLP)で解いてみた。

概要

ソルバー選択・コーディング

計算結果

参考記事