数学的に最適な寄せ鍋を考えてみた - テコテック開発者ブログ

本投稿は TECOTEC Advent Calendar 2021 の15日目の記事です。

はじめに

はじめまして。こんにちは。次世代デジタル基盤開発事業部の安彦と申します。
2021年4月に新卒で入社し、フロントエンドエンジニアをしています。

気が付けば12月も中旬、寄せ鍋が食べたい季節です。
寄せ鍋の具材は様々考えられますが、どんな具材の組合せにしたらおいしい鍋になるのでしょうか？
ということで、数学とプログラミングで最適な寄せ鍋の具材を考えてみたいと思います！

はじめに
最適な寄せ鍋とは？
数理最適化とは？
数理モデル化
具材のデータ化
Pythonでコーディング
結果１
結果２
まとめ

最適な寄せ鍋とは？

まず最適な寄せ鍋とは、
予算内で、満足度が最高になる具材を詰合せた鍋である
ということにします。
これは、数理最適化で解決できそうですね。

数理最適化とは？

数理最適化は計算機科学の１分野で、

現実社会の問題を数理モデルにして、
アルゴリズムで問題を解き、
得られた解をもとに問題の解決策を実施することです。

今回の内容に当てはめて考えると、

鍋の具材を決める問題を数理モデルにして
Pythonでプログラムを書いて
最適な寄せ鍋を決定する！！

といった流れになります。

数理モデル化

さっそくモデルを考えていきます。
与えられたアイテム集合の中から、最適なアイテムの組合せを見つけ出す問題はナップサック問題が有名です。
そこで、ナップサック問題の定式化を使います。

ja.wikipedia.org

今回のテーマに沿った形で説明します。
$I=1,2,\cdots ,N$ を具材の集合とし、
各具材 $i\in{I}$ の満足度を $s_i$ 、価格を $c_i$ 、個数を $x_i$ 、予算の上限を $C$ とすると、
次のように定式化できます。

$\require{color} \begin{align} \mathrm{maximize} \sum_{i\in{I}} \textcolor{blue}{s_{i}}\textcolor{red}{x_{i}} & \tag{1}\\ \mathrm{subject \ to} \sum_{i\in{I}} \textcolor{blue}{c_{i}}\textcolor{red}{x_{i}} & \le \textcolor{blue}{\mathrm{C}} \tag{2}\\ \textcolor{red}{x_i} & \in \{0,1, \cdots \} \ \ ( \forall i \in I ) \tag{3}\\ \end{align}$

$\textcolor{blue}{s_i, c_i, C}$ は定数、 $\textcolor{red}{x_i}$ がこの式で決定したい変数（決定変数）です。
式(1)はこのモデルの目的を示す式で、目的関数と呼ばれます。
このモデルでは満足度×個数の合計を最大化したいという意味です。
式(2,3)はモデルの条件を示す式で、制約条件と呼ばれます。
式(2)は価格×個数の合計が予算以内であるといった意味です。
式(3)は個数が0以上の整数であることを意味しています。

具材のデータ化

思いつく具材に好みで満足度を設定して、値段はおねだんノートで検索しました。
予算は千円とします。

具材i	満足度si	価格ci[円]
鶏もも肉	90	580
ねぎ	80	83
ごぼう	60	211
水菜	50	136
餅巾着	40	200
しいたけ	30	104
豆腐	10	94
春雨	5	96
予算		1,000

Pythonでコーディング

今回はPythonパッケージのPuLPを使います。
PuLPは最適化問題のモデルを入力すると、最適化ソルバーを呼び出して、解を出力してくれます。
だだし、目的関数と制約条件の左辺が定数×変数、制約条件の右辺が定数の形の一次式でなくてはなりません。
もちろんpipでインストールできます。

$pip install pulp

では、まず具材のクラスを定義します。
pulpVal は具材の個数です。後でpulpのクラスを入れるのでsetterとgetterを用意します。
getterは pulp.value メソッドで数値を取得します。

import pulp

class Item:
    def __init__(self, name, satisfaction, cost):
        self.name = name  # 具材名
        self.satisfaction = satisfaction  # 満足度
        self.cost = cost  # 価格
        self.pulpVal = None  # 個数xのpulpクラス

    def setPulpVal(self, pulpVal):
        self.pulpVal = pulpVal

    def getPulpVal(self):
        if self.pulpVal != None:
            return pulp.value(self.pulpVal)
        return -1

    def __str__(self):
        return '{:8s}\t満足度：{:3,d}点\t価格：{:4,d}円\t個数：{:3.0f}'.format(self.name, self.satisfaction, self.cost, self.getPulpVal())

先ほどの表の通りに具材をインスタンス化して、辞書に入れていきます。
printしたときの表示幅が等幅に出来なかったので、全角スペースで調整してます...

items = dict(
    tori=Item('鶏もも肉', 90, 580),
    negi=Item('ねぎ　　', 80,  83),
    gobou=Item('ごぼう　', 60, 211),
    mizuna=Item('水菜　　', 50, 136),
    mochi=Item('餅巾着　', 40, 200),
    shitake=Item('しいたけ', 30, 104),
    tofu=Item('豆腐　　', 10,  94),
    haru=Item('春雨　　',  5,  96),
)

pulpの決定変数クラスを生成&代入していきます。
辞書名とメソッド名が被ってしまいました（笑）
決定変数の種類は実数、整数、バイナリがありますが、今回は整数です。
これで、式(3)が満たされます。

for key, item in items.items():
    item.setPulpVal(
        pulp.LpVariable(
            f'x({key:s})',  # 識別名
            cat=pulp.LpInteger,  # 決定変数の種類
            lowBound=0,  # 下限
            upBound=None  # 上限
        )
    )

次にpulpの最適化モデルを生成します。
引数は名前と目的関数の向き（最大化）です。

model = pulp.LpProblem('鍋をつくるよ', pulp.LpMaximize)

次に目的関数を設定します。式(1)の通り、各具材の満足度×価格の総和を入力しています。

model.setObjective(
    sum(i.satisfaction * i.pulpVal for i in items.values())
)

次に式(2)を入れていきます。
制約条件は、model += 一次不等式 の形で入力します。
一行にイコールが二つあって違和感がありますね...

# 制約条件 : 価格の総和
model += sum(i.cost * i.pulpVal for i in items.values()) <= 1000

これでモデルの入力は完了です。
モデルオブジェクトのsolveメソッドで解を求めます。
得られた解は model.objective に入っているので、pulp.value メソッドで数値化して取り出します。
合計金額は各アイテムの金額×個数で計算します。後はお好みの形式で画面出力します。

model.solve()

totalSatisfaction = pulp.value(model.objective)
totalCost = sum(i.cost * i.getPulpVal() for i in items.values())

for i in items.values():
    print(i)

実行してみましょう。

$ python3 knapsack.py
Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

command line - /home/abiko/.local/lib/python3.8/site-packages/pulp/apis/../solverdir/cbc/linux/64/cbc /tmp/fe1b9acbbb664e88af36a54976c4ca04-pulp.mps max timeMode elapsed branch printingOptions all solution /tmp/fe1b9acbbb664e88af36a54976c4ca04-pulp.sol (default strategy 1)

実行すると、CBC MILP Solverが起動します。
これはPuLPをインストールする際に、同時にインストールされています。
PuLP内部で、数理モデルをソルバーで使われるmpsファイルとして保存し、
ソルバーを実行、得られた解をsolファイルに保存しているようです。

At line 2 NAME          MODEL
At line 3 ROWS
Problem MODEL has 1 rows, 8 columns and 8 elements
Coin0008I MODEL read with 0 errors
# 中略
Result - Optimal solution found

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00

最適解が見つかったようです。

結果１

さて、数学的に最適な寄せ鍋は、、、

具材名	満足度	価格	個数
鶏もも肉	90	580	0
ねぎ	80	83	12
ごぼう	60	211	0
水菜	50	136	0
餅巾着	40	200	0
しいたけ	30	104	0
豆腐	10	94	0
春雨	5	96	0
合計	960	996

ネギ鍋になりました笑
これでも制約条件を満たす中で、満足度が最高になる解なのです。
しかし、これでは全く役に立ちません...
モデルかパラメータがおかしいのです。

結果２

パラメータは固定して、モデルを少々調整しました。

$\begin{align} \max \sum_{i\in{I}} s_{i}x_{i} &\\ \mathrm{s.t.} \sum_{i\in{I}} c_{i}x_{i} & \le \mathrm{C} \\ x_i & \in \{ 0, 1 \} \ \ ( \forall i \in I ) \\ x_{tori} & = 1 \end{align}$

各具材の上限を１個にして、
どうしても食べたい鶏肉は必須としました。

具材名	満足度	価格	個数
鶏もも肉	90	580	1
ねぎ	80	83	1
ごぼう	60	211	1
水菜	50	136	0
餅巾着	40	200	0
しいたけ	30	104	1
豆腐	10	94	0
春雨	5	96	0
合計	260	978

以上が私の考える最適な寄せ鍋です（笑）

まとめ

今回は、最適な寄せ鍋を数理最適化の枠組みでモデル化し、Pythonで解いてみました。
数理最適化は、「資産のポートフォリオ」「従業員のシフトスケジュール」「トラックの配送経路決定」など幅広い分野で使われています。
形のあるパズルなども解くことができるのでこれからも遊んでみたいと思います。
最後まで読んで頂きありがとうございます！！