サイゼリヤメニューの最適化: Python MIP で解く

1. はじめに

1-1. 目的

この記事では、Pythonを使用してレストランのメニューアイテムを表現し、それを最適化する方法について説明します。具体的には、サイゼリヤのメニューデータを用いて最適化問題を作成し、それを解いてみます。この問題は、与えられた予算と各ジャンルの最大アイテム数の制約の下で、メニューアイテムの選択を最適化することを目指します。

1-2. データソース

この記事で使用するサイゼリヤのメニューデータは、以下のGitHubリポジトリから取得しました。

参考にしたリポジトリ:
https://github.com/marushosummers/Saizeriya_1000yen

このリポジトリには、サイゼリヤのメニューデータが含まれており、それを基に最適化問題を作成します。

2. 最適化問題の作成

2-1. 問題設定

この章では、サイゼリヤのメニューデータを用いて最適化問題を作成します。サイゼリヤでは、注文する際に「AA01」のように英語と数字を組み合わせた注文方法があります。この特性を活かして、最適化問題を設定します。

具体的には、元のデータセットから必要なデータを加工し、それを基に最適化問題を作成します。

2-2. データの取得と加工

まず、データベースからメニューデータを取得します。これにはfetch_menu_data関数を使用します。この関数は、データベースのパスを引数に取り、メニューデータをMenuItemのリストとして返します。

fetch.py

def fetch_menu_data(db_path: str) -> List[MenuItem]:
    """
    データベースからメニューデータを取得し、MenuItemのリストを返します。
    """
    rows = fetch_menu_rows(db_path)

    # 行をMenuItemのインスタンスに変換
    menu_items = [MenuItem(*row) for row in rows]

    # order_typeごとにMenuItemをグループ化
    grouped_items = defaultdict(list)
    for item in menu_items:
        grouped_items[item.order_type].append(item)

    # 各グループに対して連番を割り当てる
    for order_type_items in grouped_items.values():
        for i, item in enumerate(order_type_items, start=1):
            item.set_order_type(i)

    return menu_items

`MenuItem`class

MenuItemクラスは、サイゼリヤのメニューアイテムを表現するためのクラスです。各メニューアイテムは、一意のID、名前、カテゴリ、タイプ、価格、カロリー、塩分、そして今回使用したい注文タイプを持ちます。

menu_item.py

from typing import Dict


class MenuItem:
    """
    メニューアイテムを表すクラス。
    """

    type_prefixes: Dict[str, str] = {
        "salad": "SA",
        "appetizer": "AA",
        "pasta": "PA",
        "doria": "DG",
        "pizza": "PZ",
        "rice": "RP",
        "dessert": "DE",
        "drinkbar": "DB",
        "soup": "SU",
        "hamburg": "MT",
        "gratin": "DG",
        "alcohol": "AL",
        "chicken": "MT",
        "steak": "MT",
    }

    def __init__(
        self,
        id: int,
        name: str,
        category: str,
        type: str,
        price: float,
        calorie: int,
        salt: float,
        order_type: str = None,
    ):
        """
        MenuItemのインスタンスを初期化します。
        """
        self.id = id
        self.name = name
        self.category = category
        self.type = type
        self.price = price
        self.calorie = calorie
        self.salt = salt
        self.order_type = self.type_prefixes.get(self.type, "ZZ")

    def set_order_type(self, counter: int) -> None:
        """
        order_typeに連番を追加します。
        """
        self.order_type = f"{self.order_type}{counter:02}"

set_order_typeメソッドを使用して、メニューアイテムの注文タイプに連番を追加することができます。これにより、同じタイプのメニューアイテムを区別することが可能になります。

また、type_prefixes辞書では、各メニューのタイプに対応するプレフィックスを定義しています。これにより、メニューアイテムのタイプに基づいて注文タイプを生成することができます。元のデータには実際のメニューにはすでにないものがあるため、これらを考慮して1から連番にしています。

2-3. 最適化問題の作成

このセクションでは、solve_menu_problem関数を使用して最適化問題を作成します。この関数は、メニューアイテムのリスト、予算、および各ジャンル(ex. AA)の最大アイテム数を引数に取り、選択されたメニューアイテムのリストを返します。

まず、Modelクラスのインスタンスを作成します。これは最適化問題を表現するためのものです。

次に、各メニューアイテムに対応するバイナリ変数を作成します。これらの変数は、各メニューアイテムが選択されるかどうかを表します。

また、予算内で選択できるメニューアイテムの制約を追加します。これは、選択されたメニューアイテムの価格の合計が予算を超えないようにするためのものです。

さらに、各ジャンルに対して、そのジャンルのメニューアイテムが最大アイテム数を超えて選択されないような制約を追加します。

目的関数は、選択されたメニューアイテムのorder_typeの数値表現の合計を最大化するものです。ここで、order_type_to_num関数を使用して、order_typeを数値に変換しています。

`order_type_to_num`関数

order_type_to_num関数は、メニューアイテムのorder_typeを数値に変換するためのものです。order_typeは文字列で表現されていますが、最適化問題を解くためには数値表現が必要です。この関数はその変換を担当しています。

具体的なロジックは以下の通りです。

solve.py

def order_type_to_num(order_type: str) -> int:
    return (
        (ord(order_type[0]) - ord("A")) * 26 + (ord(order_type[1]) - ord("A")) + 1
    ) * 256 + int(order_type[2:], 16)

この関数は、order_typeの最初の2文字をアルファベットの順番に対応する数値に変換し、それらを組み合わせて一意の数値を生成します。具体的には、最初の文字のアルファベット順（ord(order_type[0]) - ord("A")）に26を掛け、2番目の文字のアルファベット順（ord(order_type[1]) - ord("A")）を加え、さらに1を加えます。これに256を掛けたものに、order_typeの3文字目以降を16進数として解釈した数値（int(order_type[2:], 16)）を加えることで、最終的な数値を得ます。

このようにして、order_typeを一意の数値に変換することで、最適化問題を解く際にorder_typeを扱いやすくしています。

これらの設定を行った後、最適化問題を解き、選択されたメニューアイテムを返します。

solve.py

def solve_menu_problem(menu_items: List[MenuItem], budget: int, max_items_per_genre: int) -> List[MenuItem]:
    m = Model("Saizeriya")
    x = {item.id: m.add_var(name=item.name, var_type=BINARY) for item in menu_items}

    m += xsum(item.price * x[item.id] for item in menu_items) <= budget

    genres = set(item.order_type[:2] for item in menu_items)
    for genre in genres:
        m += xsum(x[item.id] for item in menu_items if item.order_type.startswith(genre)) <= max_items_per_genre

    m.objective = maximize(xsum(order_type_to_num(item.order_type) * x[item.id] for item in menu_items))

    m.optimize()

    return [item for item in menu_items if x[item.id].x > 0.5]

このように、この関数を使用すると、与えられた予算と各ジャンルの最大アイテム数に基づいて、最適なメニューアイテムの組み合わせを選択することができます。具体的には、予算内で、各ジャンルの最大アイテム数を超えないように、order_typeの数値表現の合計を最大化するメニューアイテムの組み合わせを選択します。

2-4. メニューアイテムのグループ化と出力

最適化問題を解いた後、選択されたメニューアイテムをジャンルごとにグループ化し、それぞれのジャンルのメニューアイテムの数、各メニューアイテムの名前と価格、ジャンルごとの合計金額、全体の合計金額を表示します。

まず、選択されたメニューアイテムをジャンルごとにグループ化します。これはPythonのcollections.defaultdictを使用して行います。

main.py

grouped_menu_items: defaultdict = defaultdict(list)
for item in selected_menu_items:
    grouped_menu_items[item.order_type[:2]].append(item)

次に、ジャンルごとのメニューアイテムの数、各メニューアイテムの名前と価格、ジャンルごとの合計金額を表示します。

main.py

total_cost: int = 0
for genre, items in grouped_menu_items.items():
    print(f"ジャンル: {genre}, メニューの個数: {len(items)}")
    genre_cost: int = sum(item.price for item in items)
    total_cost += genre_cost
    for item in items:
        print(f" - {item.name}, 価格: {item.price}")
    print(f"ジャンル {genre} の合計金額: {genre_cost}")

最後に、全体の合計金額を表示します。

main.py

print(f"全体の合計金額: {total_cost}")

具体的な出力は以下のようになります。

ジャンル: PZ, メニューの個数: 2
 - マルゲリータ, 価格: 500
 - ペペロンチーノ, 価格: 600
ジャンル PZ の合計金額: 1100
ジャンル: PA, メニューの個数: 1
 - カルボナーラ, 価格: 700
ジャンル PA の合計金額: 700
全体の合計金額: 1800

以上で、選択されたメニューアイテムのジャンルごとのグループ化と出力が完了します。これにより、ユーザーは自分の予算内で最適なメニューの組み合わせを見つけることができます。

プロジェクトリポジトリ

今回作成したリポジトリ:
https://github.com/AzuKi9140/Saizeriya.git

• 本記事で構築したプロジェクトの全てのコードが含まれています。是非、クローンまたはフォークして、自由に使用や改変を行ってください。