Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
40
Help us understand the problem. What is going on with this article?
@YSRKEN

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

More than 1 year has passed since last update.

概要

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

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

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

参考記事

40
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
YSRKEN

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
40
Help us understand the problem. What is going on with this article?