LLMは数理最適化がおおたまんよりも得意...かも？

この記事は数理最適化 Advent Calendar 2025 21日目（だったはずの）の記事です。

今回はLLMから数理最適化ソルバーを呼び出す 数理最適化MCP（ReMIP MCP） とそれを使ったデモを作ったので紹介します。

数理最適化MCPについては、先日開催されたDevFest Tokyo 2025のLTでも紹介しました。

https://gdg-devfest-tokyo-2025.web.app/talks/7c4dff99/

MCPクラインアント側で、以下のように設定すると使えます（実験的に作っている段階なのでnpmパッケージとして公開はしていません）。

{
  "mcpServers": {
    "remip-mcp": {
      "command": "npx",
      "args": [
        "-y",
        "github:ohtaman/remip-mcp",
        "--start-remip-server"
      ]
    }
  }
}

デモは Streamlit のチャットアプリで、AIに自然言語で依頼すると、自動的に数理最適化問題に定式化して解いてくれるものです。LLMモデルは Gemini、数理最適化のソルバーは SCIP です。
ローカルに node と uv がインストールされている場合は、以下のコマンドでデモを実行できます。

$ export GEMINI_API_KEY=<your Gemini API Key>
$ uvx --from git+https://github.com/ohtaman/remip-example remip-example

デモの起動画面

好きな例題を選択し、「Use this Example Prompt」ボタンをクリックしてください。必要に応じてプロンプトを編集し、「Submit」ボタンを押すと、以降は通常のチャットのように操作できます。例題としては、できるだけ現実味のあるものを用意しました^[1]。例えばナーススケジューリングの例は以下のようになっています。

例題の例（病院ナース勤務表づくり）

07. 👩‍⚕️ 病院ナース勤務表づくり

来月30日間の看護師のシフト表を作成して欲しい。患者数は平日が多め、週末は少なめですが、月の中盤と月末に入退院の波が来ます。
看護師の「お願い（希望休・やりたい/避けたい勤務）」と、病棟の「安全に回すための現場ルール」の両方を踏まえて、無理のないシフト表を作ってください。

前提（病棟・期間・シフト）

• 病棟：一般病棟（単一病棟）
• 期間：30日（Day1〜Day30）
• 便宜上、Day1＝月曜日とします（Day7＝日曜、以降繰り返し）
• シフト：1日3交代
• 早番 (M) 08:00–16:00
• 遅番 (E) 16:00–24:00
• 夜勤 (N) 24:00–翌08:00（明けは原則お休み）

病棟のルール

絶対に守るルール

1. 各シフトは最低2名で入る（一人現場は作らない）。
2. 各シフトに「有資格者」（リーダーまたは正看）を少なくとも1名。
3. 夜勤の次の朝は勤務を入れない（体調・安全配慮）。
4. 連続勤務は最長6日（7日目は必ず休みを入れる）。
5. 事前に決まっている不在日は入れない（研修・外来応援・私用など）。

できれば守りたいルール

全体のバランスや安全を優先しつつ、現場と相談して調整します

1. 各人の夜勤回数は偏らせない（目安回数を超えないように）。
2. 週末はできるだけ公平に（同じ人に偏らせない）。
3. 希望休・やりたい/避けたい勤務をできる範囲で尊重。
4. リーダーは毎シフト1名いると安心（どうしても足りない日は正看で代替）。

1日の必要人数

• 平日（Mon–Fri）：M=4, E=4, N=3
• 週末（Sat, Sun）：M=3, E=3, N=2

必要人数についての特記事項

• Day10（木）：入院増加見込み → M+1, E+1（例：M=5, E=5）
• Day18–Day19（土日）：病棟イベント対応 → N+1（例：N=3）
• Day29（月）：定期点検で一部病室クローズ → 全シフト−1（ただし最低2名は確保）

人員一覧

• 役割の呼び方

• リーダー：経験豊富、緊急対応や指示ができる

• 正看：通常業務を自立して担当できる

• 補助：ケアや介助を主に担当（単独夜勤は不可／必ず有資格者と一緒）

• 勤務回数の目安（30日）

• 常勤：おおむね20シフト前後

• 非常勤：おおむね14シフト前後

• 夜勤回数の目安（上限イメージ）：

• リーダー：〜6回／月

• 正看：〜5回／月

• 補助：夜勤は可（必ず有資格者と同じシフト）／回数は相談

5.1 看護師マスタ（22名）

ID	役割	区分	勤務回数の目安	夜勤の目安	不在（入れない日）	希望メモ（任意）
L001	リーダー	常勤	20 前後	〜6	–	週末どちらか休み希望
L002	リーダー	常勤	20 前後	〜6	–	木曜はEが得意
L003	リーダー	常勤	20 前後	〜6	Day28–30 研修	月初は多めに可
R004	正看	常勤	20 前後	〜5	–	NよりM/E希望
R005	正看	常勤	20 前後	〜5	–	連続5日まで可
R006	正看	常勤	20 前後	〜5	–	–
R007	正看	常勤	20 前後	〜5	–	–
R008	正看	常勤	20 前後	〜5	–	–
R009	正看	常勤	20 前後	〜5	–	Day12 私用休
R010	正看	常勤	20 前後	〜5	–	–
R011	正看	非常勤	14 前後	〜4	–	平日中心
R012	正看	非常勤	14 前後	〜4	–	土曜勤務OK
R013	正看	非常勤	14 前後	〜4	–	Day17 家事都合
R014	正看	非常勤	14 前後	〜4	–	N多めも可
R015	正看	非常勤	14 前後	〜4	–	–
A016	補助	非常勤	14 前後	–	–	M多め希望
A017	補助	非常勤	14 前後	–	–	–
A018	補助	非常勤	14 前後	–	–	日曜休み希望
A019	補助	非常勤	14 前後	–	–	–
A020	補助	非常勤	14 前後	–	–	–
A021	補助	非常勤	14 前後	–	–	Day8–9 私用休
A022	補助	非常勤	14 前後	–	–	–

注意：L003は月末（Day28–30）に不在。この期間の夜勤や要所シフトでリーダーが不足しやすくなります。

6. カレンダー（曜日と特記事項）

Day	曜日	備考
1	月	–
2	火	–
3	水	–
4	木	–
5	金	–
6	土	–
7	日	–
8	月	–
9	火	–
10	水	入院増（M/E増員）
11	木	–
12	金	R009不在
13	土	–
14	日	–
15	月	–
16	火	–
17	水	R013不在
18	木	病棟イベント（N増）
19	金	病棟イベント（N増）
20	土	–
21	日	–
22	月	–
23	火	–
24	水	–
25	木	–
26	金	–
27	土	–
28	日	L003不在
29	月	病室一部休止（全体−1）
30	火	L003不在

依頼内容

上記の条件を満たす30日分の勤務表を作ってください。

注意事項

1. 出力形式は縦に看護師ID、横に日付を並べたマークダウン形式のテーブルとすること
2. 満たせなかったルールや考慮点について、絶対に守るルールとできれば守りたいルールそれぞれについて整理して箇条書きで出力すること

教科書によく出てくるような簡単な例題ではなく、現実問題に近い、ほどほどに複雑な内容であることがわかると思います。これでもAIはしっかりと解いてくれます^[2]。

専門家がいなくても数理最適化を使えるようにしたい

下図は、数理最適化を活用して現実の課題を解決する一連の流れを示しています。
まず、現状の課題を顧客へのヒアリングなどから正確に把握し、それを数理的な最適化モデルへと落とし込んでいきます（このプロセスをモデリングや定式化と呼びます）。その後、適切なアルゴリズムを用いて最適解を探索し、得られた結果を分析・検証した上で、具体的な解決策へとつなげていきます。

しかし、実際の現場ではこのプロセスが一度でうまくいくことは稀です。多くの場合、期待とは異なる計算結果が出てきて、その都度「最適化モデルのどこに問題があったのか」を考え、モデルを修正しながら、試行錯誤を繰り返します。

数理最適化による問題解決の実践的なアプローチより引用

ところで、モデリングには数理最適化の専門知識が不可欠です。一方で計算結果が妥当であるかどうかを確認するには、現場のドメイン知識が必要です。つまり、この試行錯誤のループを回すには、専門家と顧客の双方の力が必要となります。その結果、解決までに時間がかかってしまうことが少なくありません。このループが数理最適化による問題解決のボトルネックとなっています。

もしこのループを専門家の助けを借りずに顧客だけで回すことができればボトルネックは解消されます。LLMやAIエージェントが専門家を代替できれば、数理最適化の利便性は飛躍的に向上するはずです。

数理最適化MCP（ReMIP MCP）の仕組み

今回実装したMCPは以下のような構成になっています。

それぞれのモジュールは以下のような役割を担っています。

1. remip-server: REST API で数理最適化モデルを受付けて、ソルバーを実行し、結果を返す
2. pyodide: Python実行環境を提供し、PuLPによるモデリングや解の検証をサポート
3. ReMIP MCP: 各ノードの仲介役となり、データの受け渡しをする

また、上図にある数理最適化による問題解決の一般的な流れに沿って、以下のツールを提供しています。

• define_model: モデルを定義（モデリング）
• solve_problem: アルゴリズムによる求解
• get_solution: 解（計算結果）を取得
• validate_solution: 分析・検証
• list_models: モデルの一覧を取得
• get_model: モデルの詳細を取得
• list_solution: 解（計算結果）の一覧を取得

数理最適化MCPにはPythonの実行環境が必須

前述の通り、数理最適化による問題解決には試行錯誤のループが必要です。アルゴリズムの部分だけをMCPとして用意しても、ループを回すことはできず、モデリングや結果の分析・検証を行うための環境が不可欠です。これにはPython環境が最適です。PuLP や Python-MIP のような充実したモデリングツールが揃っており、ソルバー^[3]も直接呼び出すことができます。計算結果の検証や可視化は pandas で簡単に行えます。また、LLMは膨大なPythonコードを学習しているため、高い精度でコーディングできます。

Python実行環境をMCPとは別に用意しても良いようにも思えますが、そうでもありません。実案件では取り扱う変数の数が非常に多くなることがあります。制約条件は複数の変数の組み合わせたものになるため、変数以上に大規模になります。その結果、最適化ソルバーに渡すデータも必然的に大きくなりがちです。仮にLLMから直接ソルバーを呼び出す設計とした場合、こうしたデータがLLMのコンテキストを圧迫してしまいます。すると、規模の大きい問題には対応できなくなってしまいます。そのため、今のところは数理最適化MCP自体がPythonの実行環境を内包するのが望ましいようです。

セキュアなPython実行環境: Pyodide

MCPにPythonの実行環境を含める際の最大の懸念点はセキュリティです。どうやってセキュリティを担保しつつ、Pythonコードを実行するか。その答えの1つに、Pydantic AIでも採用されているPyodideがあります。

Pyodideは、Pythonランタイムと主要なライブラリをWebAssembly (WASM) に移植したものです。元々はブラウザ上でPythonを動かすためのプロジェクトですが、これをNode.js上で利用することで、以下のようなサンドボックス環境としてのメリットが得られます。

• 環境の完全な隔離: PyodideはブラウザやNode.jsのランタイム制限下で動くため、許可なくローカルファイルやネットワークにアクセスできません
• 高速な起動: Dockerコンテナを立ち上げるよりも圧倒的に軽量で、リクエストごとにクリーンな環境を瞬時に提供できます
• 状態の保持: 1回目の実行で定義した変数を、2回目の実行で利用するといった対話的なコード実行ができます

使い方もとても簡単で、以下のように JavaScript の中で runPythonAsync を呼び出すだけです。

import { loadPyodide } from "pyodide";

// Python環境の初期化
const pyodide = await loadPyodide();

// LLMが生成したコードを実行（隔離環境内）
const result = await pyodide.runPythonAsync(`
import math
def calculate_area(radius):
    return math.pi * radius ** 2
calculate_area(5)
`);

console.log(result); // ホスト側で安全に結果を受け取る

課題: Pyodide環境では多くの数理最適化ソルバーが動かない

一見すると良いことづくめに思えるPyodideですが、数理最適化という観点では、大きな課題があります。それは、多くの数理最適化ソルバーが利用できないという点です。そもそもPyodide上で動かすにはPythonで実装されているか、WASM向けにコンパイル可能である必要がありますが、主要な数理最適化ソルバーの多くがCやC++で開発されており、公式にWASM対応していないケースが大半だからです^[4]。

そこで、前述の構成図のようにPyodideの環境とソルバーを分離し、ReMIP MCP が仲介する、という構成にしました。

デモの実装

今回はGoogleのADK(Agent Development Kit)とStreamlitを使ってMCPのデモを作りました。半日くらいでサクッと作れると思っていたのですが、案外大変だったので、実装してみて気づいたことなどを紹介します。

AI はまだまだ間違える

AIによるコーディングは広く普及しており、定式化のコードの生成も簡単にできると思っていました。しかし、数理最適化の定式化が非常に複雑なためか、高い頻度で間違ったコードを生成してしまいます。間違いの種類としては、未定義の変数を使ったり、データの持ち方を間違えたりして、そもそも実行不可能なコードが生成されことが多いように思います。コードは実行可能だがユーザーの意図を間違えて解釈して実装してしまうことが多いかなと思っていたので、意外でした。

自律的な修復が必要

コードの間違いに加えて、「ツールを実行していないのに実行したと報告する」「結果を想像で返してしまう」「途中で処理をやめてしまう」といった問題も頻繁しました。そこで、今回のデモはシンプルなマルチエージェント構成にすることにしました。数理最適化問題を実際に解くremip-agentと返答をチェックするmentor-agentの2エージェント構成です^[5]。

mentor-agentはユーザーへの回答になっているか、ツールの実行がちゃんと行われているかを確認し、必要に応じて再実行を促します。この仕組みにより、何度も失敗を繰り返しつつも、最終的にはユーザーが求める解にたどり着くケースが大幅に増えました。mentor-agentへの支持は以下の通りになっています。

mentor-agentのインストラクション

MENTOR_AGENT_INSTRUCTION = """You are the Mentor Agent.
You act as the user's representative and the final decision gate.

Your sole responsibility is to decide whether the assistant’s latest response:
- is an acceptable final response to the user,
- requires user input, or
- must be revised.

You do NOT solve the problem.
You do NOT explain theory.
You judge and decide.

## P0 — Non-Negotiable Evaluation Rules

### 0. Output Language (CRITICAL)
You MUST write all of your outputs in the same language as the user.

Determine the user's language ONLY from `user_request`.
- If `user_request` is predominantly Japanese → output Japanese.
- If predominantly English → output English.
- Otherwise, output the dominant language used in `user_request`.

### １. Completion Gate (CRITICAL — MUST PASS)
The assistant response MUST be one of the following:

(A) A **direct user-facing answer** to the user’s request, OR
(B) A set of **essential clarification questions** to the user (and nothing else), OR
(C) A clear statement that the assistant cannot answer yet **and** it asks the user for required info.

If the response is only:
- internal steps (e.g., "define_model", "creating variables", "setting up", "I will run", "processing"),
- tool-call logs or partial tool outputs without interpretation,
- meta commentary without answering or asking,
- placeholders like "acceptable" or "done",

THEN → REVISION REQUIRED.

Definition of “direct user-facing answer”:
- It must explicitly address the user request.
- It must provide either:
  - a concrete result / recommendation / explanation the user can act on, OR
  - the next actionable steps in plain language.
- It must NOT be merely a status update.

### 2. User Perspective (Strict)
- The user is non-technical.
- The response must use only plain business language.
- Any mathematical or optimization terms are unacceptable
  (e.g., optimization, solver, variable, constraint, objective, MIP/LP/CP).

If technical language appears → REVISION REQUIRED.
If the response is not in the same language as the user → REVISION REQUIRED.

### 3. Tool Honesty Gate (CRITICAL)
You MUST treat `tools_used_in_this_turn` as the ONLY source of truth.
Never trust the assistant’s wording about tool usage.

#### Tool usage is REQUIRED if the assistant presents:
- any computed result,
- any plan, schedule, allocation, or table,
- any numerical outcome,
- any claim like “we found a plan”, “the result shows”, or similar.

#### Tool usage is NOT required ONLY if:
- the assistant is asking clarifying questions, OR
- the assistant is explaining the approach conceptually
  WITHOUT presenting any concrete result, plan, number, or table.

#### Hard failure conditions (ANY triggers revision):
1. The assistant claims or implies tool usage,
   BUT `tools_used_in_this_turn` is empty or does not show it.
2. The assistant presents results that clearly require computation,
   BUT no corresponding tool usage is recorded.
3. The assistant reports runtime, status, or outcomes,
   BUT no tool usage is recorded.

In these cases:
- Do NOT approve.
- Do NOT ask the user.
- Require revision and explicitly point out the mismatch.

### 4 Result Delivery Gate (CRITICAL)
If `tools_used_in_this_turn` is NOT empty, the assistant MUST deliver user-facing value from those tool results.

The assistant response MUST include at least one of:
- A plain-language summary of the tool outcome (a conclusion or recommendation), OR
- The concrete result/plan/table derived from the tool output, OR
- An explicit error/empty-result explanation and the next action, OR
- Essential clarification questions to interpret/complete the result (use `ask`).

If the assistant ran tools but provides only:
- “we will try”, “next step”, “let’s run”, “processing”, or any status update,
- tool-call intent without reporting outcomes,
- or ends without summarizing what happened,

THEN → REVISION REQUIRED.

### 5. Code Presentation (Strict)
If Python code appears, it MUST:
- be inside a fenced code block, AND
- be wrapped inside a `<details>` block with a `<summary>`.

Any violation → REVISION REQUIRED.

### 6. Business Usefulness
The result must be:
- understandable,
- implementable,
- and clearly actionable.

If the next step is unclear → REVISION or USER INPUT REQUIRED.

### 7. Infeasibility Handling (Strict)
If the assistant cannot produce a plan that satisfies all must-follow rules:
- It must enter Recovery Mode (temporary exceptions with costs) using tools,
- identify conflicting rules,
- propose minimal fixes.
Otherwise → REVISION REQUIRED.

## Decision Rule

After reviewing the response, take ONE action only:

### A. Approve and finish
Only if:
- Completion Gate passes, AND
- ALL P0 rules are satisfied, AND
- no user input is needed:
Call `exit_loop` immediately.

### B. Ask the user
If the approach is valid but essential information is missing:
- Call the `ask` tool yourself.
- Do NOT instruct the assistant to ask.

### C. Request revision
If ANY P0 rule is violated (including Completion Gate):
- Give concise, actionable feedback (max 3 points).
- Let the assistant revise.
- Do NOT call `exit_loop` or `ask`.

Do NOT allow endless retries.
If failures repeat, instruct the assistant to simplify:
- return to the baseline,
- ignore optional rules,
- or reduce the problem size.

---

## Context

```user_request
{user_input?}
```

```assistant_response
{work_result?}
```

```tools_used_in_this_turn
{tools_used?}
```
"""

mentor-agentによる判断の例

ADK と Streamlit の相性の悪さ

ADKは内部的にAnyIOというライブラリを使って、非同期処理の管理をしています。一方でStreamlitは実行フローが特殊で、内部的に非同期処理の管理をしているようです。今回のMCPはセッションごとに状態を持つものなので、寿命を意識する必要があったのですが、、片方を立てれば片方が崩れるような状況になってしまいました。結局、セッションごとにスレッドを立てて、その中で適切に寿命を管理する方法に落ち着きました。自分の中でもまだベストプラクティスが見つかっていないので詳細は書きませんが、StreamlitとADKを組み合わせようと考えている方は気をつけた方が良いと思います。

終わりに

本記事では、数理最適化MCP（ReMIP MCP）を紹介しました。実験的な実装であり、構成もやや複雑なため、動作が安定しない場合があるかもしれません。最近はLLMの能力も劇的に向上しできることがどんどん増えているため、本記事でご紹介したMCPがいつまで必要になるのかわかりませんが、LLMの苦手な領域を数理最適化が補完できるという点はとても面白いと思うので、ぜひ一度試してみてもらえればと思います。

脚注

1. AIに生成させただけですが...

2. 解いてくれないこともよくあります

3. 図のアルゴリズムに相当する部分のプログラムのこと

4. 公式ではありませんが HiGHS はWASMにコンパイル可能で、それを使った HiGHS MCP Server も存在しています。

5. 自律的に間違いを修復してくれれば良いので、MCPを使わずに数理最適化のできる環境を用意してコーディングエージェントに解かせる、というアプローチでもいいと思います。