整数計画問題で健康的な献立を見つける

#経緯
通っている大学の食堂のレシートには[三群点数法](https://www.univcoop.or.jp/service/food/three.html)（赤2点緑1点黄5点みたいなやつ）が載っている。
それを目安に食事しようね！って話なんですがこれが結構難しい。
なら††技術力††で解決しましょう👊

#健康的な食事とは？
ここでは

- 三群点数法
- 栄養素
- カロリー

を指標にすることにします。
三群点数法は男性：(2.0, 1.0, 7.0)、女性：(2.0, 1.0, 4.0)以上が目標。

#定式化
例えばカロリーは少なく、赤緑黄の点数はクリアしたいとします。
$n$個のメニューについて、そのメニューを選択するか否かをベクトル$\boldsymbol{S}$、
各メニューベクトル $(R,G,Y,E)$（ただし$R$：赤 $G$：緑 $Y$：黄 $E$：カロリー）
をメニュー分縦につなげた行列を $\boldsymbol{M}$ とすると、

```math
{\boldsymbol{S}}{\boldsymbol{M}} ={\boldsymbol{S}} \begin{bmatrix}
R_1 & G_1 & Y_1 & E_1 \\
R_2 & G_2 & Y_2 & E_2 \\
... & ... & ... & ... \\
R_n & G_n & Y_n & E_n \\
\end{bmatrix}
=(R, G, Y, E)
```

となって整数計画問題として解くことができます
目的関数は

```math
E=\left[\,\boldsymbol{S}\boldsymbol{M}\,\right]_E
=\boldsymbol{S} \left[\,\boldsymbol{M}\,\right]_E
```

制約条件は

```math

  \left\{
    \begin{array}{l}
      V_R \leq R=\boldsymbol{S} \left[\,\boldsymbol{M}\,\right]_R \\
      V_G \leq G=\boldsymbol{S} \left[\,\boldsymbol{M}\,\right]_G \\
      V_Y \leq Y=\boldsymbol{S} \left[\,\boldsymbol{M}\,\right]_Y \\
    \end{array}
  \right.

```

同様に行列$\boldsymbol{M}$に栄養素などを追加すれば各栄養素で制約することもできる。

#データ
スクレイピングで各メニューごとに

- カテゴリー
- 名前
- 点数
- カロリー
- 栄養素

を取得しjsonに格納します。(コードは割愛)


```menu_data.json
{
    "0": {
        "category": "ごはん",
        "name": "いなり",
        "R": 0.3,
        "G": 0.0,
        "Y": 0.8,
        "Energy": 87.0,
        "Protein": 1.9,
        "Lipid": 2.1,
        "Carbohydrate": 14.8,
        "Calcium": 19.0,
        "Iron": 0.4,
        "VitaminA": 0.0,
        "VitaminB1": 0.05,
        "VitaminB2 ": 0.01,
        "VitaminC": 0.0,
        "Salt": 0.5,
        "Vegetables": 0.0
    },
    "1": {
        "category": "ごはん",
        "name": "ライスＬＬ",
        "R": "...
```

#pulpで解く

下準備

```find_menu.py
import pulp
import pandas as pd
import numpy as np

full_columns = ['category', 'name', 'R', 'G', 'Y', 'Energy', 'Protein', 'Lipid', 'Carbohydrate', 'Calcium', 'Iron','VitaminA', 'VitaminB1', 'VitaminB2 ', 'VitaminC', 'Salt', 'Vegetables']
file_path = "menu_data.json"
df = pd.read_json(file_path).T.sort_index()[full_columns]
for i in full_columns[2:]:
    df[i] = df[i].astype("float")

sex = "male"
vec = (2.0, 1.0, 7.0) if sex == "male" else (2.0, 1.0, 4.0)
```

問題の定義

```find_menu.py
prob = pulp.LpProblem("nutrition", pulp.LpMinimize)  # 目的関数を最小化する

df["x"] = [pulp.LpVariable("x_" + str(i), lowBound=0, upBound=1, cat=pulp.LpInteger) for i in range(df.shape[0])]  # 変数をdfに入れる(ベクトルS)

prob += pulp.lpDot(df.Energy, df.x)  # 目的関数 -> カロリー
# prob += pulp.lpSum(df.x)  # 目的関数 -> 品数
# pulp.lpDotで内積、pulp.lpSumで総和
# 普通のsumも使えるがpulp.lpSumの方が早い

for color, value in zip(["R", "G", "Y"], vec):  # 制約条件(RGY)
    prob += pulp.lpDot(df[color], df.x) >= value
```

カロリーが少なくなるように目的関数を選択するので```pulp.LpProblem("nutrition", pulp.LpMinimize)```を使う。
変数は0か1で、x_i==1なら選ぶ、0なら選ばないとする。(同じメニューを複数選ぶのを許すならupBoundを1以上に設定する)
df.Energyは要素がメニュー数個のベクトル(各要素はカロリー)なのでdf.xとの内積は選ぶメニューの全カロリーになる。($\,\boldsymbol{S} \left[\,\boldsymbol{M}\,\right]_E$)

```find_menu.py
status = prob.solve()  # 解く

if status == 1:  # 解けたら…
    df['selector'] = pd.Series([k.value() for k in df.x])  # df.x.value()で値の取得をしてdf.selectorに入れる

df_selected = df[df["selector"] >= 1]  # 選んだメニューだけのdfを作成
print(df_selected.drop(["category", "x"], axis=1))  # categoryとxを除外して表示
for i in full_columns[2:]:
    print(i, "{0:.1f}".format(np.dot(df_selected[i], df_selected.selector)))  # トータルの値を表示

```

他にも制約条件を追加できるのでいろんなメニューを探せる

#結果
###カロリーを最小化、制約条件:RGY

```py
prob += pulp.lpDot(df.Energy, df.x)

for color, value in zip(["R", "G", "Y"], vec):
    prob += pulp.lpDot(df[color], df.x) >= value
```

| name |  R  |  G  |  Y  | Energy |
| :--  | --: | --: | --: |   --:  |
| スパイスチキンサラダ | 0.3 | 0.4 | 0 | 50 |
| 小松菜と揚げ生姜風味 | 0.2 | 0.1 | 0.2 | 30 |
| ひじき煮 | 0.3 | 0.1 | 0.4 | 55 |
| ほうれん草胡麻和え | 0 | 0.2 | 0.3 | 37 |
| 白菜胡麻和え | 0 | 0.1 | 0.2 | 20 |
| チキン塩ラーメン | 1.2 | 0.1 | 5.9 | 490 |
| 合計(6品) | 2.0 | 1.0 | 7.0 | 682.0 |

###カロリーを最小化、制約条件:RGY,ご飯×1,主菜×1,副菜・汁物×3

```py
prob += pulp.lpDot(df.Energy, df.x)

for color, value in zip(["R", "G", "Y"], vec):
    prob += pulp.lpDot(df[color], df.x) >= value

category = ["ごはん", "主菜", "副菜（小鉢）・汁物"]
for c in list(set(df["category"]) ^ set(category)):
    prob += pulp.lpSum(df.x[df["category"] == c]) == 0
for c, v in zip(category, (1, 1, 3)):
    prob += pulp.lpSum(df.x[df["category"] == c]) == v
```

| name | R | G | Y | Energy |
|:--|--:|--:|--:|--:|
| 鮭ときのこ混ぜご飯Ｓ | 0.3 | 0 | 3 | 259 |
| 鶏肉野菜スタミナ炒め | 0.8 | 1 | 3.6 | 378 |
| 小松菜と揚げ生姜風味 | 0.2 | 0.1 | 0.2 | 30 |
| 冷奴 | 0.7 | 0 | 0 | 58 |
| 白菜胡麻和え | 0 | 0.1 | 0.2 | 20 |
| 合計(5品) | 2 | 1.2 | 7 | 745 |

###品数を最小化、制約条件:RGY

```py
prob += pulp.lpSum(df.x)

for color, value in zip(["R", "G", "Y"], vec):
    prob += pulp.lpDot(df[color], df.x) >= value
```

| name | R | G | Y | Energy |
| :-- |--:|--:|--:|--:|
| 中華丼Ｌ | 1.7 | 0.7 | 8.2 | 843 |
| 茄子入り辛味噌回鍋肉 | 1.3 | 0.8 | 3.8 | 466 |
| 合計(2品) | 3 | 1.5 | 12 | 1309 |

###カロリーを最小化、制約条件:RGY,１５種類のヘルシーサラダのみ

```py
prob += pulp.lpDot(df.Energy, df.x)

for color, value in zip(["R", "G", "Y"], vec):
    prob += pulp.lpDot(df[color], df.x) >= value
df["x"] = [pulp.LpVariable("x_" + str(i), lowBound=0, upBound=50, cat=pulp.LpInteger) for i in range(df.shape[0])]  # 複数選択(50まで)を許可
prob += pulp.lpSum(df.x[df["name"] != "１５種類のヘルシーサラダ"]) == 0  # １５種類のヘルシーサラダ以外を0に
```

| name | R | G | Y | Energy |
|:--|--:|--:|--:|--:|
| １５種類のヘルシーサラダ | 0.1 | 0.3 | 0.8 | 85 |
| 合計(20品) | 2 | 6 | 16 | 1700 |


#感想
††技術力††で解決できましたね！
（本当はカロリーじゃなくて値段でやりたかったのですがどこにも記載がなくて諦めました）
ほぼスクレイピングの練習になってしまいましたがpulpの使い方がわかったのでよしとします。

[ソースコードとjson](https://github.com/ingk-124/nutrition)