数理最適化の練習問題をLLMを使って自動生成する

この記事は、数理最適化 Advent Calendar 2023 23日目の記事です。LLMと数理最適化を組み合わせた何かをつくろうということで、数理最適化の練習問題を生成する GPTs、Optima Practiceを作りました。

数理最適化のコミュニティCasual Optimizationを運営していく中で、「数理最適化が世の中に広まらない要因の一つに実践的な練習問題の不足があるのではないか？」という意見を知りました。数理最適化を実ビジネスで利用していく上で必須のスキルとして定式化がありますが、たしかに定式化の力をつけるのにちょうど良い、程よく実践的で複雑な練習問題は案外少ないです。しかし、練習問題を作成するのは結構大変です。そこで、LLMを使って自動化できないか、というのが本取り組みの趣旨になります。

作ったもの

Optima Practice は、数理最適化の練習問題を生成する GPTs です。

https://chat.openai.com/g/g-kzrYT4Kf1-optima-practice

使い方は簡単で、「数理最適化の練習問題を生成してください」ボタンを押して質問に答えると、すこし実用的で、すこし複雑な制約条件を含む練習問題を生成してくれます。

また、（きちんと解ける保証はないけれど）解答例も提示してくれます。

生成される練習問題の例

Optima Practice は、はじめに数理最適化の応用事例を列挙してくれます。ユーザーはこの中から選ぶか、独自に設定することができます。

Optima Practice は、指定された分野について、一般的な制約条件を列挙し、その中からいくつかを選択して、練習問題を生成します。練習問題には背景や目的、制約条件、ダウンロード可能なデータなどが含まれており、そのまま手を動かせる状態になっています。

以下は、実際に生成された問題の例です。それっぽい問題を生成してくれていそうです！

配送計画の例（都市間配送計画の最適化の問題を生成してくれました）

問題: 都市間配送計画の最適化

背景

ある物流会社は、複数の都市間で製品を配送しています。この会社は、輸送コストを最小化しつつ、顧客の要望に合わせた時間内に配送を完了する必要があります。都市間の距離、配送時間の制約、車両の容量などを考慮して最適な配送計画を立てる必要があります。

目的

輸送コストを最小化すると同時に、全ての都市に対して納期内に製品を配送する最適な配送計画を立ててください。

制約条件

1. 各都市へは1日に1回だけ配送が可能です。
2. 各車両の最大積載量は一定です。
3. 都市間の配送には時間がかかります。距離に応じて配送時間が異なります。
4. 特定の都市への配送には、特定の時間帯に到着する必要があります（時間窓制約）。

備考

都市間の交通状況や天候により、配送時間には変動が生じる可能性があります。また、燃料価格の変動も輸送コストに影響を与えるため、これらの要素を考慮した柔軟な計画が求められます。

データ

1. 都市間の距離
2. 各車両の積載量
3. 都市ごとの配送要望（量と納期）
4. 各都市間の平均配送時間

データを生成するコード

import pandas as pd
import numpy as np

# 都市間の距離データを生成する
np.random.seed(0)
cities = ['東京', '大阪', '名古屋', '福岡', '札幌', '仙台', '広島', '高松', '金沢', '静岡']
distance_data = {city: np.random.randint(100, 1000, len(cities)) for city in cities}
distance_df = pd.DataFrame(distance_data, index=cities)

# 対角線（同じ都市間の距離）を0に設定
np.fill_diagonal(distance_df.values, 0)

# 各車両の積載量データを生成する
vehicles = ['車両1', '車両2', '車両3', '車両4', '車両5']
capacity_data = np.random.randint(5, 20, len(vehicles)) * 100  # 500kgから2000kgの間
capacity_df = pd.DataFrame(capacity_data, index=vehicles, columns=['積載量(kg)'])

# 都市ごとの配送要望（量と納期）データを生成する
demand_data = np.random.randint(1, 10, len(cities)) * 100  # 100kgから900kgの間
deadline_data = np.random.randint(1, 5, len(cities)) * 24  # 24時間から96時間の間
demand_df = pd.DataFrame({'配送要望(kg)': demand_data, '納期(時間)': deadline_data}, index=cities)

# 各都市間の平均配送時間データを生成する
delivery_time_data = (distance_df / np.random.randint(40, 80, (len(cities), len(cities))))  # 速度40-80km/hで計算
delivery_time_df = delivery_time_data.round(2)  # 時間を小数点以下2桁で丸める

# CSVファイルとして保存
distance_file = '/mnt/data/distance_data.csv'
capacity_file = '/mnt/data/capacity_data.csv'
demand_file = '/mnt/data/demand_data.csv'
delivery_time_file = '/mnt/data/delivery_time_data.csv'

distance_df.to_csv(distance_file)
capacity_df.to_csv(capacity_file)
demand_df.to_csv(demand_file)
delivery_time_df.to_csv(delivery_time_file)

(distance_file, capacity_file, demand_file, delivery_time_file)

人員計画の例（レストランのシフト計画最適化の問題を生成してくれました）

問題: レストランのシフト計画最適化

背景

あるレストランチェーンは、複数の店舗で効率的なシフト計画を立てる必要があります。顧客の来店パターン、従業員のスキル、勤務可能時間などを考慮して、最適な人員配置を行う必要があります。

目的

人件費を抑えつつ、各店舗のサービス品質を維持するために、最適なシフト計画を立ててください。

制約条件

1. 各店舗には、特定の時間帯に必要な最小人数があります。
2. 従業員は一定の勤務時間制限を持っています（週の最大労働時間など）。
3. 従業員のスキルセットに応じて、特定の職務に割り当てられます。
4. 従業員の勤務可能時間帯には個人差があります。

備考

顧客の来店パターンは曜日や時間帯によって異なるため、柔軟なシフト計画が必要です。また、従業員の満足度を考慮し、連続勤務の回避や休憩時間の確保も重要です。

データ

1. 各店舗ごとの時間帯別最小人数
2. 従業員の勤務時間制限
3. 従業員のスキルセット
4. 従業員の勤務可能時間帯

# 人員計画のためのデータを生成

# 各店舗ごとの時間帯別最小人数データを生成
store_names = ['店舗A', '店舗B', '店舗C']
time_slots = ['朝', '昼', '夕方', '夜']
min_staff_data = np.random.randint(2, 6, (len(store_names), len(time_slots)))
min_staff_df = pd.DataFrame(min_staff_data, index=store_names, columns=time_slots)

# 従業員の勤務時間制限データを生成
employee_names = [f'従業員{i}' for i in range(1, 21)]  # 20人の従業員
max_hours_data = np.random.randint(20, 41, len(employee_names))  # 週20時間から40時間
max_hours_df = pd.DataFrame(max_hours_data, index=employee_names, columns=['最大勤務時間(週/時間)'])

# 従業員のスキルセットデータを生成
skills = ['調理', '接客', '清掃', '管理']
skills_data = np.random.randint(0, 2, (len(employee_names), len(skills)))
skills_df = pd.DataFrame(skills_data, index=employee_names, columns=skills)

# 従業員の勤務可能時間帯データを生成
availability_data = np.random.randint(0, 2, (len(employee_names), len(time_slots)))
availability_df = pd.DataFrame(availability_data, index=employee_names, columns=time_slots)

# CSVファイルとして保存
min_staff_file = '/mnt/data/min_staff_data.csv'
max_hours_file = '/mnt/data/max_hours_data.csv'
skills_file = '/mnt/data/skills_data.csv'
availability_file = '/mnt/data/availability_data.csv'

min_staff_df.to_csv(min_staff_file)
max_hours_df.to_csv(max_hours_file)
skills_df.to_csv(skills_file)
availability_df.to_csv(availability_file)

(min_staff_file, max_hours_file, skills_file, availability_file)

スポーツチームの戦略最適化の例（サッカーチームのフォーメーション最適化の問題を生成してくれました）

問題: サッカーチームのフォーメーション最適化

背景

あるサッカーチームは、次の大会に向けて最適なフォーメーションを決定する必要があります。選手のスキル、体力、ポジション適性などを考慮し、チームの得点力と守備力のバランスを最適化する必要があります。

目的

チームの総合力を最大化するフォーメーションを決定してください。

制約条件

1. 各ポジションには特定の数の選手を配置する必要があります（例：フォワード2人、ミッドフィールダー4人など）。
2. 各選手には、ポジションごとの適性スコアがあります。
3. 選手の体力を考慮し、長時間のプレーに耐えられる選手のみをスターティングメンバーとして選出します。
4. 特定の選手間には相性があり、一緒にプレーすることでチームのパフォーマンスが向上することがあります。

備考

チームの戦略には、攻撃重視、守備重視、バランス型などがあり、これらの戦略によって最適なフォーメーションは異なります。また、対戦相手の特性も考慮する必要があります。

データ

1. 選手のポジションごとの適性スコア
2. 選手の体力スコア
3. 選手間の相性スコア
4. チームの戦略オプション

import pandas as pd
import numpy as np

# スポーツチームの戦略最適化のためのデータを生成

# 選手のデータを生成
players = [f'選手{i}' for i in range(1, 21)]  # 20人の選手
positions = ['フォワード', 'ミッドフィールダー', 'ディフェンダー', 'ゴールキーパー']

# ポジションごとの適性スコア
position_scores = np.random.randint(50, 100, (len(players), len(positions)))

# 選手の体力スコア
stamina_scores = np.random.randint(50, 100, len(players))

# 選手間の相性スコア
compatibility_scores = np.random.randint(0, 10, (len(players), len(players)))
np.fill_diagonal(compatibility_scores, 0)  # 自己相性は0

# データフレームの作成
position_df = pd.DataFrame(position_scores, index=players, columns=positions)
stamina_df = pd.DataFrame(stamina_scores, index=players, columns=['体力スコア'])
compatibility_df = pd.DataFrame(compatibility_scores, index=players, columns=players)

# CSVファイルとして保存
position_file = '/mnt/data/position_scores.csv'
stamina_file = '/mnt/data/stamina_scores.csv'
compatibility_file = '/mnt/data/compatibility_scores.csv'

position_df.to_csv(position_file)
stamina_df.to_csv(stamina_file)
compatibility_df.to_csv(compatibility_file)

(position_file, stamina_file, compatibility_file)

自然言語処理オタクの喜びそうな問題の例（ニュース記事のトピック分布最適化の問題を生成してくれました）

問題: ニュース記事のトピック分布最適化

背景

あるニュース配信サービスは、ユーザーに提供するニュース記事のトピック分布を最適化する必要があります。ユーザーの関心や過去の閲覧データに基づいて、トピックの多様性と関連性を最大化することが求められます。

目的

ユーザーの満足度を最大化するために、ニュース記事のトピック分布を最適化してください。

制約条件

1. 各トピックには、配信する記事の数に上限があります。
2. ユーザーごとに関心のあるトピックには重みが異なります。
3. 各記事にはトピックの適合度があり、高い適合度を持つ記事を優先的に配信する必要があります。
4. 特定のトピックは、一定期間内に配信量を制限する必要があります（例：政治関連のニュース）。

備考

ユーザーの関心は時間とともに変化するため、定期的な最適化が必要です。また、偏ったトピックの配信は避け、多様性を保つことが重要です。

データ

1. 各記事のトピック適合度
2. ユーザーごとのトピック関心度
3. トピックごとの記事配信上限
4. 時間制限内の特定トピックの配信量制限

# 自然言語処理オタクのためのニュース記事トピック分布最適化のためのデータを生成

# 記事とトピックのデータ
articles = [f'記事{i}' for i in range(1, 101)]  # 100個の記事
topics = ['政治', '経済', 'スポーツ', '科学', '文化', '国際']

# 各記事のトピック適合度
topic_fit_scores = np.random.rand(len(articles), len(topics))

# ユーザーごとのトピック関心度
users = [f'ユーザー{i}' for i in range(1, 51)]  # 50人のユーザー
user_interest_scores = np.random.rand(len(users), len(topics))

# トピックごとの記事配信上限
topic_limits = np.random.randint(5, 15, len(topics))

# 特定トピックの時間制限内配信量制限
limited_topics = {'政治': 10, '国際': 10}  # 例：政治と国際のトピックはそれぞれ10記事まで

# データフレームの作成
topic_fit_df = pd.DataFrame(topic_fit_scores, index=articles, columns=topics)
user_interest_df = pd.DataFrame(user_interest_scores, index=users, columns=topics)
topic_limit_df = pd.DataFrame(topic_limits, index=topics, columns=['配信上限'])

# CSVファイルとして保存
topic_fit_file = '/mnt/data/topic_fit_scores.csv'
user_interest_file = '/mnt/data/user_interest_scores.csv'
topic_limit_file = '/mnt/data/topic_limit_scores.csv'

topic_fit_df.to_csv(topic_fit_file)
user_interest_df.to_csv(user_interest_file)
topic_limit_df.to_csv(topic_limit_file)

(topic_fit_file, user_interest_file, topic_limit_file)

技術詳細

OpenAI の GPTs を使って、 UI 上でポチポチ設定しました。Instructions に以下の内容を設定しています。

Instructions　の設定内容

Goal and Role:
Optima Practiceは、日本語の、数理最適化の練習問題を生成するものです。Optima Practice の生成する練習問題は、実践的であり、現実問題でよくある複雑な制約条件を含みます。Optima Practice の生成する問題には、現実問題に非常に近い、仮想的なデータも含みます。


Constraints:
1. 日本語でやりとりをしてください
2. 生成する練習問題は、タイトル、背景、目的、制約条件、備考、データ を含みます。
3. 練習問題は、ある程度複雑で現実的な制約条件を含む、実践的な内容である必要があります
4. 練習問題に含まれる制約条件は、数理最適化の基本的な教科書に載っている簡単なものだけではなく、その分野特有の事情や人間的な内容など、現実に即した制約条件である必要があります
5. 問題を解くために必要なデータは全て提供する必要があります
6. 練習問題の備考には、その分野特有の事情など、その分野で数理最適化を活用する上で参考となる情報を記載します
7. 生成するデータはcsv形式で、ダウンロード可能なものとします
8. 生成するデータはランダムな値ではなく、現実によくありそうな仮想的なデータである必要があります
9. 解答例は、「目的関数」、「制約条件」、「実行可能なコード」、「ポイント」を含みます
10. 解答例に含まれる「目的関数」には、日本語の説明と、数式による表現が含まれます
10. 解答例に含まれる「制約条件」には、日本語の説明と、数式による表現が含まれます
10. 解答例に含まれる「目的関数」では、数式内で日本語を使ってはいけません
11. 解答例に含まれる「制約条件」では、数式内で日本語を使ってはいけません
12. 解答例に含まれる「実行可能なコード」では、PuLP、networkX、scikit-learn、scipy、numpy、pandas などのライブラリを使用できます
13. 解答例に含まれる「実行可能なコード」では、生成したデータを使用できます
14. 解答例において、制約条件は数式と説明文で表現してください


Instructions:
1. はじめに、Optima Practice は、練習問題を作成する分野、業界もしくは応用事例を選択するか、独自の設定を入力するよう、ユーザーに尋ねてください
2. 次に、ユーザーの選択した分野に基づいて、数理最適化の応用事例を列挙し、ユーザーに選択を促してください。opt_problems.json からの知識を活用できます
3. 次に、選択した応用事例において、現実に必要となりうる制約条件を列挙し、ユーザーに提示してください
4. 次に、列挙した制約条件のいくつかまたはすべてを含めた練習問題を生成してください
5. 次に、練習問題を解くのに必要なデータを列挙してください
6. 次に、ユーザーに具体的なデータが必要か尋ねてください。必要であれば、列挙したデータをcsv形式で生成し、ユーザーがダウンロードできるようにします
7. 次に、生成したデータのcsvファイルを読み込み、マークダウンのテーブル形式で表示してください
8. 次に、生成したデータで、練習問題に含まれる制約をすべて表現でき、練習問題を解くことができるか確認してください
9. データに不足がある場合は、追加のデータをcsv形式で生成し、ユーザーがダウンロードできるようにしてください。また、マークダウンのテーブル形式で表示してください
10. 次に、ユーザーに「解答例を表示」するか尋ねてください
11. ユーザーが「解答例を表示」を選択した場合、Optima Practice は、解答例を提示してください


Format of "練習問題":
## 問題: <問題のタイトル>

<背景>

### 目的

<目的>

### 制約条件

<制約条件>

### 備考

<その分野特有の事情など、その分野で数理最適化を活用する上で参考となる情報>

### データ

1. <データ名1>
2. <データ名2>
...

<データのダウンロードURL>

UI上で Chat Bot との会話を通じて大枠を作って最後調整するだけで完成、という体験はとても面白かったです。

今後に向けて

現時点では、生成された練習問題がどれくらい良い問題なのか確認できていません。そこで以下のような観点で生成された問題を確認しながら Instruction を調整していけると良いなと思っています。

1. 練習問題のバラエティ: 数値だけ違うほぼ同じ問題ばかり出ていたりはしないか
2. 練習問題の難易度: 簡単すぎる問題や解けない問題どれくらい存在しているか
3. 解答例の質: 解答例の説明がどれくらい正しいか、またコードは実行可能か

また、生成された問題をどこかに登録して公開できるような仕組みをつくるのも面白いかもしれません。