LLM を活用した計画(数理最適化の解)の説明

※ 本記事は数理最適化 Advent Calendar 2025 12 月 5 日の記事です *1．よろしければ，過去の記事もご覧いただけると幸いです．

こんにちは，研究開発室の福井です．研究開発室においてオペレーションズ・リサーチ(OR)のビジネス活用について研究を行っております．今回は，数理最適化により得られた計画(問題の解)が「何故そのようになったのか?」を説明するために大規模言語モデル(LLM)と数理的な手法を組み合わせたアプローチについて解説します．

課題: 数理最適化により得られた計画(解)に対して説明が必要
- Minimal Unsatisfiable Subset (MUS)による説明
- 既存手法の問題点
独自のアプローチの開発
今後の課題
まとめ
参考文献
Appendix
- 既存のコードベースをできるだけ変更しないための工夫

課題: 数理最適化により得られた計画(解)に対して説明が必要

以前の記事，「オペレーションズ・リサーチ(の数理最適化)における説明可能性」でも言及したように，OR の手法によって得られた計画案(解)に対しても説明が必要となる場面が度々生じます．例えば，とある製造計画を出力する OR のシステムが図 1 上段のような結果を返したとします．図中のタスク B が締め切りから遅れてしまいました．このとき，システムのユーザ(我々にとってのお客様)は「なぜ締め切りを守れないのか?」という疑問を抱くこととなります．計画の規模(製造機器の数やタスクの数)が小さければ入力データを順に追えば原因を特定することができますが，実問題では数百〜数千件のタスクを扱うためそれも容易ではありません．また，ユーザの全員がシステムの裏にある数理モデルの詳細を把握しているわけではないため，事前に原因の当たりを付けることも容易ではありません．

この例のように，ユーザが自力で締め切り遅れ(あるいは，その他の違和感のある解)の原因を特定できなければ開発元であるフレクトに原因を問い合わせることになります(図 1 下段)．この時，フレクト側では，OR のモデルを開発した担当者が入力データと出力結果を目視確認し，どの入力/制約条件が問い合わせ内容と関連しているのかを調べます．しかし，大量に存在するパラータの中から原因を探し出す必要があるため，この作業は長い時間を要する負担の大きなものとなってしまいます*2．また，ユーザが出力結果に対して疑問を抱くたびに担当者に問い合わせることとなるため，ユーザにとっても体験が良くありません．

この課題を解決するためには，ユーザが自力で「なぜ計画がそうなったのか? (その解になったのか?)」を人間の専門家の手を借りずに自力で理解できるようにするための仕組みが必要となります．そのためには，システムが何らかの方法を用いてユーザに対して出力結果に対する説明を行う必要があります(図 2)．得られた計画を説明するための方法には主に，

可視化による説明
言葉による説明

の 2 種類が考えられます．可視化による説明では，「どのタスクの間に依存関係があるか?」，「どの機器がどのタスクを実施できるか?」，「各タスクにどのような制約があるか?」といった様々なの有用な情報をシステムの画面上で可視化することでユーザに対して理解を補助します(図 3)．一方，言葉による説明では，「なぜ計画が〇〇にならなかったのか?」という問いに対して具体的にどの制約条件がユーザの要望と干渉しているのかを伝えることで解の説明を行います(例: 図 2 右下の吹き出し)．

可視化による説明は直感的で便利です．一見これだけでも十分なように思われますが，タスクが大量に存在するような実問題では，複数の条件が干渉することがあるため可視化された補足情報があったとしてもそれらを目で追うのが大変になってしまいます．また，可視化による説明手法には汎用性が低いという問題があります．実問題の種類によって計画の可視化方法は大きく変わります．それに伴い，問題にあった説明手法も大きく変わってしまいまうため，新たな種類の実問題に取り組むたびに適切な説明手法の考案に時間を要することとなります．一方，言葉による説明は，可視化ほどの直感的ではありませんが，裏にある数理モデルの情報があればいつでも使えるためより汎用性が高くなります．

図 2. ユーザが自力で「何故計画がそうなったのか?」を理解できる仕組みの開発．

現在，研究開発室では言葉による説明の手法の開発に取り組んでいます．以降では，その概要を解説します．

Minimal Unsatisfiable Subset (MUS)による説明

言葉による説明手法にも様々なアプローチが考えられますが，経験上，実際にお客様からいただくお問い合わせの多くは Minimal Unsatisfiable Subset (MUS; Liffiton & Sakallah, 2008) を解析する問題に帰着することが多いです *3．これは数理モデルの中から矛盾する制約条件の部分集合を見つけ出すための手法です．図 4 に MUS の簡単な例を示します．図 4 は簡単な job-shop scheduling の問題です．図 4a の計画に対して「Job2-3 のタスクをもっと早く開始したいが，なぜそうならないのか?」という質問が与えられたと仮定します．この質問に対して MUS を計算した結果が図 4b です．図 4b の結果より，

Job2-1 は時刻 t = 3 からしか開始できない
Job2-1 → Job2-2 の依存関係がある (Job2-1 の完了後にしか Job2-2 を実施できない)
Job2-2 → Job2-3 の依存関係がある

という 3 つの制約条件が干渉して望み通りの結果にならないことがわかります．図 4 のような小規模な問題だとこの機能は不要に見えるかもしれませんが，計画内のタスクの数が数百〜数千ともなると非常に有用な機能となります．

上記のように， MUS は便利なツールであることがわかりました．これだけでも説明機能は事足りそうに見えますが，現場のユーザが使うにはまだハードルがあります．「なぜ〇〇にならないのか? (〇〇になってほしい)」という要望から MUS を計算するには，この要望を適切な数式に置き換えてやる必要があります．先の例では図 4b の query: (V) StarTime(Job2-3) < 6が置き換えられた数式に相当します．この変換処理は，OR の基礎知識を持っておりモデルの実装をよく把握している人間にとっては比較的容易な作業である一方，ユーザにとってはその限りではありません．そのため，OR の基礎知識を持った誰かがユーザと MUS 計算機能との間に入りユーザの要望を数式に変換し，更には MUS の計算結果をわかりやすくユーザに伝える必要があります(図 5)．これでは，相変わらず OR の専門家が必要となり，ユーザが自力で「なぜそうなったのか?」を理解できるようにするというゴールが達成できません．そこで，ユーザと MUS 計算機能(図 5 の Symbolic Module)との仲介役の人間を，近年ものすごい勢いで発達している大規模言語モデル(LLM)に置き換えるというアイデアが出てきます．

既存手法の問題点

以前の記事の Contrastive explanations の節でも紹介したように，(OR の専門家ではない)ユーザと OR に関連した計算機能との間を LLM で仲介するアイデアはすでに既存研究においていくつか提案されています．代表的なものには OptiChat (Chen et al., 2024)，EOR (Zhang et al., 2015)，TRACE-CS (Vasileiou & Yeoh, 2025) 等が存在しており，それらの実装も公開されています．そうなると，後は公開されている実装を流用すればやりたいことは達成できそうに見えます．しかし，実際にはそのままでは実務には使えない問題が存在します．

一番の問題は，どのように LLM にモデルと計画のパラメータ(データ)の情報を伝えているかという点にあります．OptiChat の実装を確認すると，数理最適化の教科書のサンプルコードのように 1 ファイルにべた書きされたモデルのコードとパラメータが LLM の prompt (もしくは chat 履歴)にそのまま貼り付けられていることがわかります(図 6)．これは，他の既存研究の実装においても同様のようでした *4．一方，実務用のシステムを実装する場合，パラメータやモデルは何らかのクラスとしてまとめるため数理最適化の教科書のサンプルコードのような書き方とはならず，実装はある程度の規模のコードベースに成長しているものと思われます *5．実務での数理最適化のコードの書き方に関しては，他の方々のブログ等でも言及されています(cf. 1, 2, 3, 4)．また，実問題は多くのパラメータを伴っており，それら全てを prompt に含めるやり方は現実的ではありません．研究ならば図 6 のやり方でも良かったですが，実務で扱うコードベースや大量のパラメータに対してはまた別のアプローチを考えてやる必要があります．

図 6. OptiChat におけるコードとパラメータの扱い方(OptiChat の実装より引用)

独自のアプローチの開発

課題に対する打ち手: Vibe coding ツールのようにコードベースとデータを参照する

先述の通り，最適化モデルのコードやパラメータの全てを prompt に持たせるやり方は現実的ではありません．その代わりにどうすれば良いでしょうか? ここで，昨今流行りの vibe coding ツールが参考となります．Vibe coding ツールはコードベース内の様々なファイルを適宜参照しつつ必要なコードを生成してくれます．これと同様の仕組みがあれば，既存の数理最適化のシステムのコードベースやデータ等を参照しつつ，ユーザの要望を制約条件の数式に変換する処理(コード)を自動生成できそうです．ただし，以下のように，これらの vibe coding ツールをそのまま使えない事情があります．

(筆者が知る限りでは) vibe coding の機能はすぐに import して使えるメジャーな package になっておらず，自前のシステムの処理に組み込みづらい *6
コードベース上のファイルを好き勝手に編集してほしくない
- 納品物が勝手に書き換わってしまうのは困ります
コードは生成してほしいが，任意のコードを実行できるようにはしたくない．できることに制限を設けたい

そこで，今回は vibe coding に似たような機能を時前で用意し，それをユーザの要望を制約条件に変換する workflow の中に組み込むことにしました．これに加えて，出力された MUS に対して補足説明を行う workflow も作成しました．全体の処理の流れは図 7 のようになります．今回の開発する workflow は様々なファイルを参照する必要があるため RAG 関連の機能が充実している Llamaindex を使用しました *7．図 7 に登場する各 workflow は Llamaindex の Agent Workflow 機能を用いて実装しています．

そして図 7 の処理により，具体的には図 8 の例のような説明を行うことが可能となります．図 8 では，タスク A が締め切りから遅れています．一方で，機械 2 と同じ種類の機械 1 が空いているのになぜそちらにタスク A が割り当てられないのかを質問しています．以降の節では，この図 8 の質問が各 workflow の中でどのように処理されていくのかを見ていきます．実際に出力された回答の詳細は後の節において紹介します．

モジュール 1: 質問解釈 Workflow

質問解釈 Workflow は，与えられた質問が計画と関連しているかどうかの確認と，質問文から質問者が何を望んでいるのか(どういう状態の計画を求めているのか?)を解釈します．前者の処理では，与えられた質問文に登場するワードを入力データ(json)，json schema，設計書等から調べることで，その質問文が計画と関連しているかどうかの簡単な二値分類を行います．これにより，「今日の天気は?」等の計画と無関係な質問を弾くことが可能となります．以下は，質問解釈 Workflow (の中の LLM) が質問を判定している様子です．ここでは，Workflow の内部の処理のログを抜粋しています．そして後者の処理は，ユーザから与えられた質問文をユーザが望む状態を表す制約条件に近い表現の言葉に変換します．

(注意:【***】で表記された文字列は ID や特定のフレーズを伏せたものです．以降でも同様です)

LLM が質問の内容を判定する様子(クリックで展開)

2025-11-13T00:12:36.164320

質問を解釈しています...

---

2025-11-13T00:13:31.763739

User question is valid: 【タスク A の ID】 が 【機械 1 の ID】 に割り当てられないのはなぜですか?

---

2025-11-13T00:13:31.764663

Rationale:
質問は「【タスク A の ID】 が 【機械 1 の ID】 に割り当てられないのはなぜですか？」と、特定の ID 間の割り当てがなされなかった理由を尋ねています。これは【機械】・コンポーネントの割当やスケジュール上の決定、制約・競合の原因を問うものであり、スケジューリング／最適化に該当します。詳細な原因特定のためには、スケジュールデータや制約情報の確認が必要です。

次に質問内容に関する調査が行われ最終手にユーザから与えられた質問文が，ユーザの要望を表す文に変換されます．以下のログ

LLM がユーザの要望を解釈する際のログ(クリックで展開)

2025-11-13T00:15:22.720386

- 【タスク A の ID】: BoundItem（binding_id: 【タスク A の ID】）。5 つの ScheduleItem（各々は GeneralTestItem 相当）をまとめたエントリ。含まれるテストはそれぞれ test_id / item_id と duration を持ち、全項目の lot は【機械のロットの ID】、variation は【機械の種類の ID】に一致。各項目の due_date は 2026-03-23 slot 0、required_resources（資源 ID）が設定されており、同一時間帯での資源競合や【機械】の空き時間によって割当可否に影響する。assignment_options や fixed_assignment は特別な固定・専有指示を含まず null のため、ソルバーや既存スケジュール状況に依存して割当が決まる。合計所要時間（項目の duration 合計）は約 19.5（入力値の合計）。soft_group が項目ごとに設定されているため、グループ化・順序制約のヒントになる可能性がある。
- 【機械 1 の ID】: Machine（machine_id: 【機械 1 の ID】）。スケジューリング上のワーカー（試験【機械】）。lot: 【機械のロットの ID】、variation: 【機械の種類の ID】（BoundItem 内の項目と一致）。start_time は 2025-09-22 slot0 で利用開始、end_time は未指定（null）。designated_categories / prohibited_categories は空、is_for_evaluation / with_high_accuracy は false。役割としては上記のテスト群を割り当て可能な候補だが、実際に割り当てられるかは【機械】の他タスクでの既存割当、当該時間帯の空き、各項目の必要資源の競合、ソルバーのバインド処理ルールなど複数の要因に依存する。

---

2025-11-13T00:15:37.697991

Refined question: 【タスク A の ID】を【機械 1 の ID】に割り当ててほしい.

に示した通り，LLM による調査を経た上でユーザの要望は

【タスク A の ID】を【機械 1 の ID】に割り当ててほしい.

であると LLM により解釈されました．

説明対象である既存の最適化システムにおいて，入力データ(json)とその schema は Pydantic によって定義されています．また，入力ファイルに関するドキュメントは Markdown によって書かれています．Llamaindex はこれらの入力用 json ファイル，Pydantic から export した json schema (これも json です)， Markdown に特化した JSONQueryEngine，JSONNodeParser，JSONReader，MarkdownNodeParser 等のコンポーネントを提供してくれており，これらを用いて VectorStoreIndex を作成することで入力データやドキュメントにアクセスするための RAG を比較的素早くにを構築することができます *8 ．

モジュール 2: Coding Workflow

質問解釈 Workflow により，ユーザからの質問文が「【タスク A の ID】を【機械 1 の ID】に割り当ててほしい.」という要望を表す文に変換されました．次に来る Coding Workflow はこの要望に対応した制約条件を組み立てるためのコードを生成します．Llamaindex には CodeSplitter，CodeHierarchyAgentPack 等のにコード理解に特化したコンポーネントが存在します *9 ．Coding Workflow はそれらを用いて構築された RAG，更にはいくつかの自前で用意した専用 tool を介してコードや計画問題の内容を理解します．これらのコード理解の仕組みは，既存の最適化システムのコードベースに対して何らかの変更を要求しないため，その既存システムに対して後付けで導入することができます (他にも元のコードベースを維持するための工夫があります．詳しくは Appendix を参照ください)．

まず，Coding Workflow はコードと問題インスタンスを理解するための計画を作成します．そして，Plan-and-Solve (Wang et al. 2023) や ReWoo (Xu et al. 2023) 等で提案されているような「計画立案 → 実行」の流れに沿って入力データやコードベースの調査を行います *10．以下が，生成された調査計画となります．生成された計画の各ステップには「どの tool を使うか?」と「その tool で何を調べるか?」の情報が含まれています．

データとコードの調査計画(クリックで展開)

2025-11-13T00:19:00.970881

Plan:

- ['code_summary_lookup', 'general_test_bm25_query_engine']: レビューフィードバック確認: 過去の PR/レビューコメント、差分要約、既知の問題点を確認する検索クエリを実行する。具体的クエリ例: 'constraint_expression_factory レビュー', 'CPMpyReadOnlyModelWrapper review', PR タイトルやコミットメッセージの BM25 検索。期待成果: レビューメモ（注意点、命名規則、既知バグ、テスト期待値）。バックアップ: フィードバックが見つからない場合は PR/コミット履歴を BM25 で広く検索。 (レビューフィードバックがあれば実装方針に直接影響するため最優先で確認する。)
- ['search_component_by_id']: 対象 ID のコンポーネント特定（1 つずつ検索）: search_component_by_id を用いて以下を個別検索する: '【タスク A の ID】' および '【機械 1 の ID】'. 期待成果: 各 ID のタイプ（ItemId/WorkerId/Group など）、関連オブジェクト参照（duration, active flag, 所属グループ 等）のメタデータ。バックアップ: 直接ヒットしない場合は先頭/末尾 8~12 文字での部分一致検索や BM25 に切り替える。 (正しく割当制約を作るには、対象 ID が何を表すか（ScheduleItem なのか Worker なのか）を明確にする必要がある。ID 検索は一つずつ行うのが確実。)
- ['code_vector_store_lookup', 'code_hierarchy_lookup']: CPMpyReadOnlyModelWrapper API 探索: リポジトリ内でクラス 'CPMpyReadOnlyModelWrapper' と以下のメソッドを探す: item_id2item, worker_id2worker, get_worker_var, worker2idx, get_item_active_indicator, get_start_time_var 等。期待成果: 各メソッドの正確なシグネチャ（引数型／返り値型）、例（使い方スニペット）。バックアップ: クラスが直ちに見つからない場合は 'item_id2item' 等のメソッド名で横断検索。 (実際の式を作成するために model の公開メソッドと型を正確に知る必要がある。)
- ['code_summary_lookup', 'code_vector_store_lookup', 'general_test_bm25_query_engine']: 実装パターン検索: 制約関数（constraint*expression_factory）で 'アイテムを特定ワーカーに割当てる' 既存例を検索する。クエリ例: 'assign .* to .\_ worker', 'get_worker_var .\* worker2idx', 'item_id2item'、既存ファイル内の類似実装を 1-3 件抽出。期待成果: 具体的なコードスニペット（ファイル名・行数付き）と実装上の注意点（inactive item の扱い等）。バックアップ: 直接例がない場合は Appendix の例をテンプレートにする旨を明示した実装案を作成。 (既存パターンに合わせることで一貫性とレビュー受け入れの確度が上がる。)
- ['cpmpy_cheat_sheet_query_engine_tool', 'code_vector_store_lookup']: 具体的コード設計（スニペット作成）: タスク 2 と 3 の結果を元に、constraint_expression_factory に挿入する最短の CPMpy Expression スニペットを設計する。想定形: target_item = model.item_id2item(ItemId(...)); machine_var = model.get_worker_var(target_item); target_worker = model.worker_id2worker(WorkerId(...)); constraint = machine_var == model.worker2idx(target_worker)。さらに item が inactive の場合の前提や guard を明記。期待成果: 日本語コメント付きの挿入可能なコードブロックと前提条件。バックアップ: worker2idx が無い場合の代替（許容インデックス集合を使う等）を提示。 (実装段階で必要な最小限のコードを早期に確定することでレビュー負荷を軽減できる。)
- ['general_test_vector_store_query_engine', 'code_summary_lookup']: テストと PR 準備: 最小入力データでの単体テストを作成するため、既存のテストケース／テンプレートを検索。クエリ例: 'GeneralTestProject minimal sample', 'constraint unit test', 'constraint_expression_factory test'。期待成果: ユニットテスト案（入力データ、期待解）、PR 用説明テンプレート、実装ノート（前提／既知制限）。バックアップ: サンプルが見つからない場合はモック GeneralTestProject を手作りし、テストを作成する。 (変更を安全に導入するために自動テストとドキュメントを用意する必要がある。)

---

2025-11-13T00:19:00.972554

Running search tasks

...... (※ 以降では Plan 内のステップが上から順に実行されます)

そして，上記の調査を完了した後に LLM がまとめた調査結果が以下のようになります．この中には，質問に登場する ID の意味や与えられた要望を実装するために必要となる各オブジェクトの情報が列挙されています．

LLMによる調査の結果(クリックで展開)

2025-11-13T00:30:20.027333

Generated guide:

## Implementation Guide

### Summary

要求“【タスク A の ID】を【機械 1 の ID】に割り当ててほしい”を CPMpy ラッパー経由で制約式として表現するための実装ガイド。対象 ID は BoundItem（ScheduleItem として扱う）と Worker（【機械】）である。割当は model.get_worker_var(item) == model.worker2idx(worker) の等式で表現し、アイテムが非アクティブなら制約を適用しないガード式 ((active==0) | (var==widx)) を付けるのが標準パターン。Expression に対しては必ず set_description を呼ぶ。TimeManager は時間不等式を扱う場合のみ必要。

### Component Explanation

- 【タスク A の ID】 : BoundItem（binding_id）。内部に複数のサブアイテムを持つが、ドメインルール上は単一の ScheduleItem として扱う。items[*] に item_id, duration (float)、required_resources、assignment_options、fixed_assignment、due_date 等を含む。
- 【機械 1 の ID】 : Worker（【機械】）。machine_id、lot、variation、start_time (DateSlot)、end_time、designated/prohibited categories、flags（is_for_evaluation, with_high_accuracy）等のメタデータを持つ。割当先として model.worker_id2worker で取得する。
- CPMpyReadOnlyModelWrapper : モデルラッパー。主要メソッド: item_id2item, worker_id2worker, get_worker_var, worker2idx, get_item_active_indicator, get_start_time_var を提供し、ScheduleItem/Worker を CPMPy 変数にマッピングする役割を持つ。NO_WORKER_IDX を定数として持つ。
- ScheduleItem / BoundItem : ScheduleItem は抽象エンティティ（GeneralTestItem/【Xxx】TestItem/BoundItem/SensorTestGroup のいずれか）。BoundItem は外側の単一 ScheduleItem として扱うこと。duration() メソッドで所要時間を返す（float で返る可能性あり）。
- TimeManager / time_converter : DateSlot <-> TimePeriod、float-duration <-> TimePeriod の変換を行う。時間不等式（開始 + duration <= period など）を組む場合に使用する。丸め規則（切り上げ／切り捨て）は実装依存。
- Expression (cpmpy.expressions.core.Expression) : CPMpy の制約式オブジェクト。生成後に set_description(str) を必ず呼び、ExplainableSolution 等での説明やデバッグに用いる。

### Key Information

- Data Structure (想定 JSON フィールド)

  - BoundItem: binding_id, items[*]{item_id, duration (float), soft_group, required_resources, assignment_options, fixed_assignment, due_date}
  - Worker/【機械】: machine_id, lot, variation, start_time{date,slot}, end_time, designated_categories, prohibited_categories, is_for_evaluation, with_high_accuracy

- API Methods (CPMpyReadOnlyModelWrapper: 主要想定シグネチャ)

  - item_id2item(item_id: ItemId) -> ScheduleItem
  - worker_id2worker(worker_id: WorkerId) -> Worker
  - get_worker_var(item: ScheduleItem) -> IntVar
  - worker2idx(worker: Worker | WorkerId) -> int
  - get_item_active_indicator(item: ScheduleItem) -> BoolVar
  - get_start_time_var(item: ScheduleItem) -> IntVar
  - 定数: NO_WORKER_IDX (int)
  - Expression: .set_description(str) を呼ぶ慣習あり

- Object Access（典型フロー）

  1. target_item = model.item_id2item(ItemId("【タスク A の ID】"))
  2. target_worker = model.worker_id2worker(WorkerId("【機械 1 の ID】"))
  3. machine_var = model.get_worker_var(target_item)
  4. widx = model.worker2idx(target_worker)
  5. active_flag = model.get_item_active_indicator(target_item)

- Constraint Patterns (CPMpy 表現)
  - 単一割当: machine_var == model.worker2idx(target_worker)
  - アクティブガード付き: (active_flag == 0) | (machine_var == widx)
  - 複数候補: machine_var == idx1 | machine_var == idx2 | ...
  - 時間不等式: get_start_time_var(item) + item.duration() <= time_converter.slot2period(DateSlot(...))

### Implementation Guidance

実装手順（順序）

1. 対象オブジェクト取得
   - target_item: ScheduleItem = model.item_id2item(ItemId("【タスク A の ID】"))
   - target_worker: Worker = model.worker_id2worker(WorkerId("【機械 1 の ID】"))
2. モデル変数を取得
   - machine_var: IntVar = model.get_worker_var(target_item)
   - widx: int = model.worker2idx(target_worker)
   - active_flag: BoolVar = model.get_item_active_indicator(target_item)
3. 制約式の構築（推奨パターン）
   - constraint: Expression = (active_flag == 0) | (machine_var == widx)
   - constraint.set_description("(Q) Assign(【タスク A の ID】 -> 【機械 1 の ID】)")
4. 返却: return constraint

コードパターン（テンプレート）

# model.item_id2item / worker_id2worker で対象を取得

target_item: ScheduleItem = model.item_id2item(ItemId("【タスク A の ID】"))
machine_var: IntVar = model.get_worker_var(target_item)
target_worker: Worker = model.worker_id2worker(WorkerId("【機械 1 の ID】"))
widx: int = model.worker2idx(target_worker)

# アクティブでなければ制約は無視（ガード）し、アクティブなら指定【機械】に等しいことを要求

constraint: Expression = (model.get_item_active_indicator(target_item) == 0) | (machine_var == widx)
constraint.set_description("(Q) Assign(【タスク A の ID】, 【機械 1 の ID】")

実装時の注意点（禁止事項に留意）

- CP-SAT へ直接切替えを提案しない。CPMpy と Expression を用いること。
- 実装は既存の型注釈を参照して静的型ヒントに従うこと。動的な存在チェックや例外処理の追加はここでは提案しない。

### Gaps & Limitations

- リポジトリ内の正確なファイルパス（cpmpy_wrapper.py の完全ソース）や行番号は未取得。これにより一部シグネチャや戻り値型は推定に依存している。
- worker2idx のオーバーロード（Worker|WorkerId 受け取り）や NO_WORKER_IDX の正確な定義はソース参照が無ければ不確定。
- TimeManager.slot2period の丸め規則（float→TimePeriod の扱い）は未確認。duration が float のときの厳密な取り扱いが不明。
- constraint_expression_factory の既存 PR 差分やユニットテストの実体は取得できていない（テストテンプレートは Appendix に基づく提案）。

### Confidence Assessment

- ID 種別判定（【タスク A の ID】は BoundItem、【機械 1 の ID】 は Worker）: HIGH（検索結果が一貫）
- CPMpyReadOnlyModelWrapper の主要メソッド存在と役割: MEDIUM→HIGH（複数ソースの要約に一貫性ありがソース抜粋は限定的）
- 割当式パターン（machine_var == worker2idx(worker)）: HIGH（サンプル・テンプレートが複数存在）
- アクティブガード ((active == 0) | (var == widx)): MEDIUM（一般的で推奨されるパターンだが active の意味付けは実装依存）
- 時間変換（duration float -> TimePeriod）に関する挙動: LOW（丸め規則未確認）

### Further Research Suggestions

優先度順のターゲット調査項目:

1. scheduler/general_test/solver/cpmpy_wrapper.py の完全ソース取得（目的: 正確な型注釈, NO_WORKER_IDX, worker2idx シグネチャ確認）
2. scheduler/time_converter.py の slot2period/period2slot 実装確認（目的: float duration の TimePeriod 変換と丸め規則確認）
3. BoundItem の実体コード（scheduler/solver/component.py 等）で内部サブアイテムの既存制約適用例を確認（目的: BoundItem 外側のみで良いかの確定）
4. constraint_expression_factory に関する既存 PR/ユニットテストの差分取得（目的: 実装スタイルと set_description 運用ルールの確認）

失敗・未試行のツール:

- PR 差分の直接取得は未成功（PR/コミット ID 不明）

代替手法:

- 上記ファイル群の抜粋を提供いただければ、低信頼項目を高信頼に置き換えて最終実装例を作成します。

### Source References

情報源（Appendix B の検索タスク要約）:

- constraint_expression_factory レビュー要約 (Task 1) — code_summary_lookup, BM25 検索サマリ
- search_component_by_id による 【タスク A の ID】 (BoundItem) と 【機械 1 の ID】 (Machine) の JSON レスポンス (Task 2)
- CPMpyReadOnlyModelWrapper のメソッド群に関する検索サマリ (Task 3)
- Assign-to-worker パターンと例示コード（Task 4, Task 5）
- constraint_expression_factory 用テンプレートと複数の実例（Appendix E）

（必要であれば、上記ファイルの抜粋を提供いただくことで本ガイドの不確定部分を完全確定できます。）

そして，上記の調査結果をもとに自動生成されたコードは以下のようになります．このコードは数理モデルや入力データに関わるいくつかのオブジェクトを受け取り，最後に制約条件のオブジェクト(CPMpy の Expression オブジェクト)を返す関数となっています．

調査結果から自動生成されたコード(クリックで展開)

import datetime

import cpmpy as cp
from cpmpy.expressions.core import Expression

from data_model.common import DateSlot, Slot
from data_model.general_test import GeneralTestProject
from scheduler.common_type import ItemId, WorkerId
from scheduler.general_test.solver.cpmpy_wrapper import (
    BoolVar,
    CPMpyReadOnlyModelWrapper,
    IntVar,
)
from scheduler.solver.component import ScheduleItem, Worker
from scheduler.solver.solution import ExplainableSolution, ItemAssignment
from scheduler.time_converter import TimeManager


def constraint_expression_factory(
    model: CPMpyReadOnlyModelWrapper,
    input_data: GeneralTestProject,
    solution: ExplainableSolution,
    time_converter: TimeManager,
) -> Expression:
    """Generate constraint expression from user request.

    Parameters
    ----------
    model : CPMpyReadOnlyModelWrapper
        A wrapped CPMpy model
    input_data : GeneralTestProject
        input data for a general-test scheduling problem
    solution : ExplainableSolution
        A current solution for the scheduling problem
    time_converter : TimeManager
        A object for time conversion (TimePeriod <-> DateSlot)

    Returns
    -------
    Expression
        A CPMpy expression representing the constraint requested by the user
    """
    # Requested constraint: "【タスクAのID】 を 【機械1のID】 に割り当ててほしい."
    # <YOUR_CODE_STARTS_HERE>
    # Retrieve target schedule item (BoundItem treated as ScheduleItem)
    target_item: ScheduleItem = model.item_id2item(
        ItemId("【タスクAのID】")
    )

    # Retrieve target worker (Machine)
    target_worker: Worker = model.worker_id2worker(
        WorkerId("【機械1のID】")
    )

    # Get the model variable that indicates which worker (Machine) is assigned to the item
    machine_var: IntVar = model.get_worker_var(target_item)

    # Convert worker object to its index used in the machine_var domain
    target_worker_idx: int = model.worker2idx(target_worker)

    # Get active indicator for the item (guard). If the item is inactive, constraint should be ignored.
    active_flag: BoolVar = model.get_item_active_indicator(target_item)

    # Construct the guarded assignment constraint:
    # either the item is inactive (active_flag == 0) OR machine_var equals the target worker index
    constraint: Expression = (active_flag == 0) | (machine_var == target_worker_idx)

    # Set a descriptive text for explainability/debugging
    constraint.set_description(
        "(Q) Assign (【タスクAのID】) -> 【機械1のID】"
    )
    # <YOUR_CODE_ENDS_HERE>

    return constraint

生成されたコードは Python の str 型として保持され，その後コードの内容が解析されます．この解析により，「許可されていない Built-in 関数を使っていないか?」，「許可していない package を import していないか?」等のチェックが行われます *11．この仕組みにより，何らかの危険な処理を行わないようコードの挙動を制限しています．そして，チェックが済んだコード(str 型のデータ)はコードオブジェクトにコンパイルされた上で実行されます．この一連の処理を経て，直接ファイルを編集したり出力したりすることなく上記のコードから比較的安全に Expression を生成します．コードやその実行結果に問題があれば LLM によるレビューが行われ，コードの修正とレビューのサイクルが回ります．改めて，これらの処理の流れを図示すると下図 9 のようになります *12 ．

図 9. Coding Workflow 内での処理の流れ(Llamaindex による可視化)．

モジュール 3: MUS を計算する Symbolic Module

先の Coding Workflow により得られた制約条件(Expressionオブジェクト)を用いて MUS を計算します．MUS の計算処理には，CPMpy が提供する機能を使用しています *13．以下が，今回のケースで算出された MUS です．5 つの制約条件が干渉している事がわかります．

- (Constraint) The start time of ScheduleItem(id=【タスク A の ID】) cannot be earlier than the start time of worker(id=【機械 1 の ID】) (The start time of the worker is t=114)
- (Constraint) ScheduleItem(id=【タスク A の ID】) cannot be performed after ScheduleItem(id=【タスク B の ID】) on the same worker. (Hints: This constraint is likely to be imposed by damage constraints)
- (Constraint) The start time of ScheduleItem(id=【タスク B の ID】) is fixed to t=220
- (Constraint) The start time of ScheduleItem(id=【タスク C の ID】) is fixed to t=129
- (Constraint) The start time of ScheduleItem(id=【タスク D の ID】) is fixed to t=165

※ 補足: 上記の MUS は，制約条件を実装する際に事前に用意されたテンプレートのメッセージです(下記のコード例の description を参照)．

制約条件に対するテンプレートメッセージの設定例(クリックで展開)

# 例 1
self.add_soft_constraint(
    constraint=(self.get_start_time_var(item) == start_time),
    description=(
        f"(Constraint) The start time of ScheduleItem(id={item.item_id()}) "
        f"is fixed to t={start_time})"
    ),
)

# 例 2
self._wrapper.add_soft_constraint(
    constraint=(
        self._wrapper.get_same_worker_indicator(
            preceding_item, succeeding_item
        ).implies(
            self._wrapper.get_end_time_expr(succeeding_item)
            <= self._wrapper.get_start_time_var(preceding_item)
        )
    ),
    description=(
        f"(Constraint) ScheduleItem(id={succeeding_item.item_id()}) "
        "cannot be performed after "
        f"ScheduleItem(id={preceding_item.item_id()}) on the same worker. "
        "(Hints: This constraint is likely to be imposed by damage constraints)"
    ),
)

この MUS を図解すると図 10 のようになります．

モジュール 4: 説明 Workflow

入力データとモデルの関係，システム内での前処理の内容等をよく理解していればこれら MUS の情報だけでも説明は十分に感じるかもしれません．しかし，多くのエンドユーザにとってはまだ十分ではありません．どのような経緯でこれらの制約条件がモデルに設定されたのかを補足説明する必要があります(加えて，t=*** 等の抽象的な時刻の表現も不親切です)．

数理最適化のモデルは，大量の入力データや複雑な前処理を通して組み立てられます．そのため，何がきっかけで MUS に登場した制約条件が設定されたのかを特定するためには，複数の異なる情報(ドキュメント，入力データ，コード，計算時の前処理のログ，etc.)を参照する必要があります．ここでも Coding Workflow のときと同じく，LLM に先に調査計画を立てさせた上で説明に必要な情報を収集させます．今回のケースでの調査計画を以下に示します．

説明のための調査計画(クリックで展開)

Plan:

仮説（要約）: 1) Worker(【機械 1 の ID】) の利用可能開始が t=114 に固定されているため、ScheduleItem(【タスク A の ID】) はそれ以前に開始できない。2) 【タスク A の ID】と【タスク B の ID】の順序制約は DamageRule（損傷ルール）によるもので、【タスク】 を実施すると【機械】が損傷し【タスク A の ID】が実施不可になるため同ワーカー上で【タスク】の後に実施できない。3-5) 【タスクの種類】系の複数アイテムは固定開始時刻（t=220,129,165）を持ち、外部予約や設備/リソース制約で動かせない可能性が高い。全体として、ワーカー可用性、割当可能ワーカー一覧、DamageRule/DependencyRule、固定開始（fixedStart）とログが原因の主要要素と推定。

- ['search_component_by_id（ScheduleItem/Worker の JSON 抽出）']: （Constraint Decomposition）以下の MUS 制約で参照されるオブジェクト（ScheduleItem および Worker）の JSON を取得し、startTime/earliestStart/latestStart/fixedStart 等のフィールドを抽出する。対象 ID: 【タスク A の ID】, 【タスク B の ID】, 【タスク C の ID】, 【タスク D の ID】, Worker 【機械 1 の ID】 (数式的に何が比較されているか（変数・演算子・値）を明確化するため。)
- ['search_component_by_id（Worker）']: Worker(id=【機械 1 の ID】) の可用性フィールド（開始時刻、可用ウィンドウ、arrivalTime 等）を確認し、t=114 の意味（利用開始/到着など）を特定する。 (制約(1) の直接原因がワーカー可用性かを確定するため。)
- ['get_assignable_worker_ids']: ScheduleItem(id=【タスク A の ID】) の割当可能ワーカー一覧を取得し、【機械 1 の ID】 が含まれているか確認する。 (そもそも【機械 1 の ID】が割当可能でない場合は別の原因（【機種】適合性など）があるため。)
- ['get_damage_rule_ids']: 【タスク A の ID】 と 【タスク B の ID】 の間の DamageRule を検索し、存在・方向性・属性（禁止順序、修復時間、例外等）を確認する（両方向で確認）。 (ヒントにあるとおりダメージ制約が順序禁止の主要因である可能性が高いため。)
- ['get_dependency_rule_ids']: 【タスク A の ID】 と 【他のタスク】 の間の依存ルール（DependencyRule）も確認し、別の前後関係が存在しないかを調べる。 (順序制約は DamageRule だけでなく DependencyRule によることもあるため。)
- ['search_component_by_id（各 ScheduleItem）']: 固定開始時刻が指定されている【タスク】（t=220,129,165）の各 ScheduleItem オブジェクトを取得し、fixedStart フラグ、assignedResource/reservation 情報、理由となるメタデータを確認する。 (固定開始の根拠（外部予約・設備割当・顧客依頼等）を把握するため。)
- ['convert_integer_time_t_to_date_slot']: 時間整数 t=[114,129,165,220] を DateSlot に変換し、実際の日時・AM/PM スロットを把握する。 (実時間で確認することで業務的理由（午前/午後/特定日）を説明しやすくなるため。)
- ['search_component_by_id（【タスク A の ID】 の duration と time window）', 'convert_integer_time_t_to_date_slot']: 【タスク A の ID】 を Worker【機械 1 の ID】に割り当てた場合、【他のタスク】の固定アイテムと時間的に衝突（重複）するかを確認する。具体的には 【タスク A の ID】の所要時間/期間を取得して、GT-M の固定開始とオーバーラップするか判定する。 (割当不可の直接原因が時間重複か順序禁止かを区別するため。)
- ['check_if_shared_machine_exists']: 【タスク A の ID】と【タスク B の ID】が同一ワーカーに共存可能な共有ワーカー（shared machine）が存在するか確認する。 (共通割当可能ワーカーが存在しない場合、同ワーカー順序の話は無意味となるため。)
- ['debug_log_file_query_engine_tool']: 該当 ScheduleItem IDs と Worker ID を含むデバッグログを検索し、割当失敗時に出力されるメッセージ（damage-rule violation, fixed-start conflict 等）の抜粋を抽出する。 (実行時にどの制約が評価されて割当が拒否されたかをログで確認するため。)
- ['json_schema_query_engine_tool']: 入力 JSON スキーマで ScheduleItem, Worker, DamageRule, DependencyRule, fixedStartTime, assignableWorkers, TimePeriod の定義を確認して、各フィールドの正式な意味と許容値を把握する。 (取得した JSON の解釈ミスを防ぐため。)
- ['code_summary_lookup / code_vector_store_lookup']: サーバー/ライブラリ内で DamageRule と DependencyRule を評価しているコードを検索し、コメントや実装から業務的根拠（例: 特定のテスト実施後は外観検査不可等）を抽出する。 (技術的・業務的理由は実装やドキュメントに記載されている場合があり、説明に信頼性を持たせるため。)

上記の調査結果をもとに，最終的にユーザに提示するための説明文を LLM に生成させます．生成された説明文(のサマリー版の抜粋)は以下のようになります．入力ファイル(json)上のどの field，どのルールが MUS 内の制約条件に影響しているのかが説明されています．

### Short Summary:

要約（MUS ＝割当と矛盾する主原因）

1. 【機械】上での時間重複

- 問題：同一【機械】に時間が重なる試験を同時に配置できない。BoundItem の所要時間（合計 19.5 ＝約 39 DateSlot）が【機械】の利用開始と既に固定された開始時刻により収まらないため重複が発生。
- 関連フィールド：Machine 【機械 1 の ID】 start_time = 2025-09-22 (AM)、BoundItem 【タスク A の ID】 items[].duration = 19.5、【タスク C の ID】の FixedAssignment.start_time = 2025-10-01 (PM)、【タスク D の ID】 = 2025-10-27 (PM)

2. 固定開始試験間のギャップ不足

- 問題：固定開始済み試験（2025-10-01、2025-10-27、2025-12-04）の間に BoundItem の長時間を完全に収められないため割当不可。
- 関連フィールド：上記 FixedAssignment.start_time と BoundItem の duration

3. DamageRule による近接禁止/分離時間

- 問題：DAMAGE-RULE-000948063-1-23 / -24 が 【タスク B の ID】 → BoundItem の組合せに適用され、同一【機械】で直後に実施することを禁止または一定の分離を要求しているため割当不可。
- 関連フィールド：DamageRule IDs、【タスク B の ID】 FixedAssignment.start_time = 2025-12-04 (AM)

変更可能な対処案（優先度高）

- 固定開始時間の解除／移動（対象 【タスク】項目）
- 【機械】の start_time を前倒し
- BoundItem の duration を短縮
- DamageRule の属性確認（禁止／分離時間の緩和）
- 別【機械】への割当

重要な入力フィールド（MUS を生んでいるもの）

- 各 FixedAssignment.start_time（3 件）: 2025-10-01、2025-10-27、2025-12-04
- Machine 【機械 1 の ID】 start_time = 2025-09-22 (AM)
- BoundItem 【タスク A の ID】 duration = 19.5
- DamageRule IDs: DAMAGE-RULE-000948063-1-23, -24

より詳細な全ての説明文(クリックで展開)

## Answer:

### User Request:

【タスク A の ID】を【機械 1 の ID】に割り当ててほしい.

### Short Summary:

要約（MUS ＝割当と矛盾する主原因）

1. 【機械】上での時間重複

- 問題：同一【機械】に時間が重なる試験を同時に配置できない。BoundItem の所要時間（合計 19.5 ＝約 39 DateSlot）が【機械】の利用開始と既に固定された開始時刻により収まらないため重複が発生。
- 関連フィールド：Machine 【機械 1 の ID】 start_time = 2025-09-22 (AM)、BoundItem 【タスク A の ID】 items[].duration = 19.5、【タスク C の ID】の FixedAssignment.start_time = 2025-10-01 (PM)、【タスク D の ID】= 2025-10-27 (PM)

2. 固定開始試験間のギャップ不足

- 問題：固定開始済み試験（2025-10-01、2025-10-27、2025-12-04）の間に BoundItem の長時間を完全に収められないため割当不可。
- 関連フィールド：上記 FixedAssignment.start_time と BoundItem の duration

3. DamageRule による近接禁止/分離時間

- 問題：DAMAGE-RULE-000948063-1-23 / -24 が 【タスク B の ID】 → BoundItem の組合せに適用され、同一【機械】で直後に実施することを禁止または一定の分離を要求しているため割当不可。
- 関連フィールド：DamageRule IDs、【タスク B の ID】 FixedAssignment.start_time = 2025-12-04 (AM)

変更可能な対処案（優先度高）

- 固定開始時間の解除／移動（対象 GT-M 項目）
- 【機械】の start_time を前倒し
- BoundItem の duration を短縮
- DamageRule の属性確認（禁止／分離時間の緩和）
- 別【機械】への割当

重要な入力フィールド（MUS を生んでいるもの）

- 各 FixedAssignment.start_time（3 件）: 2025-10-01、2025-10-27、2025-12-04
- Machine 【機械 1 の ID】 start_time = 2025-09-22 (AM)
- BoundItem 【タスク A の ID】 duration = 19.5
- DamageRule IDs: DAMAGE-RULE-000948063-1-23, -24

### Detailed Explanation:

ご依頼「BoundItem を Machine 【機械 1 の ID】に割り当てる」が現在のデータとルールと矛盾している（MUS ＝最小矛盾集合を構成している）理由を、各制約ごとに分かりやすく説明します。該当する入力フィールド（JSON の項目名）とオブジェクト ID も明記します。

1. 同一【機械】上での時間重複禁止（既に固定開始がある試験との重複）

- 制約の内容：同じ【機械】（Machine）には時間が重なる複数の試験を割り当てられません（同時実施不可）。
- 影響する入力フィールド／オブジェクト（ID）と値：
  - 【タスク C の ID】の FixedAssignment.start_time = 2025-10-01 (PM)
  - 【タスク D の ID】の FixedAssignment.start_time = 2025-10-27 (PM)
  - Machine 【機械 1 の ID】の start_time = 2025-09-22 (AM)
  - BoundItem 【タスク A の ID】の items[].duration 合計 = 19.5（内部換算で約 39 DateSlot 相当）。BoundItem の FixedAssignment.start_time = null（固定開始なし）。
- なぜ問題か：
  - 上記の【機械】開始可能日時と既に固定された開始時刻の間に、BoundItem の所要時間（長時間）を収めることができません。例えば【機械】が 2025-09-22 (AM) から使えるとしても、BoundItem を最も早く置くと 2025-10-01 (PM) に固定された【タスク C の ID】と時間が重なります。よって「同一【機械】での時間重複禁止」により割当は矛盾します。

2. 固定開始された試験群の間に収められない（ギャップ不足）

- 制約の内容：同じ【機械】に複数の固定開始の試験が存在する場合、それらの間の空き時間に新しい試験を完全に収められる必要があります。所要時間がその空きに入らなければ割当不可です。
- 影響する入力フィールド／オブジェクト（ID）と値：
  - 【タスク C の ID】の FixedAssignment.start_time = 2025-10-01 (PM)
  - 【タスク D の ID】の FixedAssignment.start_time = 2025-10-27 (PM)
  - 【タスク B の ID】の FixedAssignment.start_time = 2025-12-04 (AM)
  - BoundItem 【タスク B の ID】の items[].duration 合計 = 19.5（約 39 DateSlot 相当）
- なぜ問題か：
  - 固定開始の間隔（2025-10-01、2025-10-27、2025-12-04）に対して BoundItem の必要時間が長く、いずれかの固定試験と時間的に重なるため、同一【機械】上での配置が不可能になります。

3. DamageRule（損傷検出／禁止ルール）の適用による順序・近接制約

- 制約の内容：特定の試験の組合せに対して DamageRule が適用されると、同一【機械】で直後に実施することを禁止したり、一定の分離時間を要求したりします。これにより同一【機械】への割当が制限されます。
- 影響する入力フィールド／オブジェクト（ID）と値：
  - DamageRule: DAMAGE-RULE-000948063-1-23
  - DamageRule: DAMAGE-RULE-000948063-1-24
  - これらのルールは【タスク B の ID】 → BoundItem 【タスク A の ID】の組合せに適用されているログが確認されています。
  - 【タスク B の ID】 の FixedAssignment.start_time = 2025-12-04 (AM)
- なぜ問題か：
  - 【タスク B の ID】が 2025-12-04 (AM) に固定されている【機械】に対して、DamageRule によりその直後や一定時間内で BoundItem を実施することが禁止または制限されているため、同一【機械】への割当が矛盾します。

要点（どの入力フィールドが MUS を生んでいるか）

- 各試験の FixedAssignment.start_time（固定開始時間）
  - 【タスク C の ID】の FixedAssignment.start_time = 2025-10-01 (PM)
  - 【タスク D の ID】の FixedAssignment.start_time = 2025-10-27 (PM)
  - 【タスク B の ID】の FixedAssignment.start_time = 2025-12-04 (AM)
- 【機械】（Machine）オブジェクトの start_time
  - Machine 【機械 1 の ID】の start_time = 2025-09-22 (AM)
- 試験の所要時間（items[].duration の合計）
  - BoundItem 【タスク B の ID】の items[].duration 合計 = 19.5（内部換算で約 39 DateSlot 相当）
- DamageRule（禁止／分離ルール）
  - DAMAGE-RULE-000948063-1-23
  - DAMAGE-RULE-000948063-1-24

ユーザが修正可能で、この要求を満たすために変更を検討できる入力フィールド

- 各 GT-M 項目の FixedAssignment.start_time（固定を解除するか、別の日時に変更する）
  - 【タスク C の ID】、【タスク D の ID】、【タスク B の ID】
- Machine 【機械 1 の ID】の start_time（【機械】の開始可能日時の前倒し）
- BoundItem 【タスク A の ID】の items[].duration（試験所要時間の見直し）
- DamageRule（DAMAGE-RULE-000948063-1-23 / DAMAGE-RULE-000948063-1-24）の属性確認・見直し（禁止か分離時間かを DTO で確認）
- 別の【機械】（Machine）への割当（別の【機械】に移す）

以上が、今回の割当要求を矛盾させている主要な MUS 制約と、それらがどの入力フィールド／オブジェクト（ID）に基づいているかの説明です。

## Symbolic Information:

### Query Constraint:

(Q) Assign (【タスク A の ID】) -> 【機械 1 の ID】

### MUS Constraints:

- (1) (Constraint) The start time of ScheduleItem(id=【タスク A の ID】) cannot be earlier than the start time of worker(id=【機械 1 の ID】) (The start time of the worker is t=114)
- (2) (Constraint) ScheduleItem(id=【タスク A の ID】) cannot be performed after ScheduleItem(id=【タスク B の ID】) on the same worker. (Hints: This constraint is likely to be imposed by damage constraints)
- (3) (Constraint) The start time of ScheduleItem(id=【タスク B の ID】) is fixed to t=220
- (4) (Constraint) The start time of ScheduleItem(id=【タスク C の ID】) is fixed to t=129
- (5) (Constraint) The start time of ScheduleItem(id=【タスク D の ID】) is fixed to t=165

今後の課題

以上までに示したように，LLM と MUS の計算機能を組み合わせることで非専門家でも「なぜその計画(解)になったのか?」を理解できる機能を作れることがわかりました．ただ，この機能の開発はまだ始まって間もなく，いくつかの解決すべき課題が存在します．

回答生成までの所要時間が長い

各 workflow は複数の処理のステップ構成されており，各ステップの中で LLM の API を呼び出しているため，全体の処理に 1 時間程の時間を要しています(MUS の計算は意外と速く，今回のケースだと 2〜3 分程度で完了しています)．特に，Plan-and-Solve の枠組みの処理に非常に長い時間を要しており，この処理時間をいかに高速化するか? そもそも，API の呼び出し回数をもっと減らせないか? 等を検討していく必要があります．実用的な観点から考えると，対応する制約条件のコードが既知のよくある類の質問(FAQ)に対しては専用の UI を用意してやり，LLM によるコード生成の工程をスキップするといったアプローチも有効かもしれません．

※ 補足: 人力/目視確認で同様の調査や説明作業を行う場合，OR の担当者(専門家)が 2〜4 時間ほど拘束されることも多々ありました．解説用の図 8 では計画表の一部のみを切り出しているため簡単そうな作業に見えるかもしれませんが，実際には数十台の機械，1000〜2000 件のタスクの中から原因を特定する必要があります．その点を踏まえると，1 時間放置すれば説明が自動で出てくる上に説明作業の属人化も解消できるというのは大きな進歩であるとも捉えられます．

回答の安定性と prompt のチューニング

1 つ前の課題とでも言及したように，何度も LLM を呼び出すことで最終的な回答の生成を行っています．そのせいか，最終的に生成される回答が処理を実行するたびにブレやすくなる印象があります．また，ハルシネーションが発生することもあり，回答文において json schema には定義されていないはずの field やドキュメントに存在しないフレーズが説明文に登場することもあります．より良い回答を得るためには，基本的には LLM に与える prompt を改良するところから手を付けていくことになると思いますが，workflow の中で何度も異なる prompt で LLM を呼び出しているため，手を加えなければならない prompt が多数存在しています．これら全ての prompt を手動で改良/メンテしていくのもあまり現実的ではないため，将来的は DSPy や TextGrad 等の prompt 最適化技術を導入することで，手動での prompt 管理を不要にしていけるのが望ましいと考えています．また，prompt 最適化を実現するには評価方法やデータセット等についても検討が必要となります．

実行可能な解に対する説明

今回は，実行不可能な要望に対する説明を自動で行えるようにしましたが，「実行可能な要望だが諸事情でそうならなかった」というケースも度々発生するものと予想されます．今後は，こういったハッキリとした答えを提示しづらいケースに対する説明をどのように行っていくかについても考えていきたいと思います．

まとめ

最後まで読んでいただきありがとうございました．今回は，現在開発中の LLM と数理的な手法(MUS の計算)を組み合わせて計画の説明を行うアプローチについて紹介させていただきました．処理が非常に遅い，挙動が安定しない等の課題も残っていますが，今後の研究を通してより使いやすい物にしていきたいと考えています．Flect では，今回紹介したような説明の技術なども取り入れることで，お客様にとってより付加価値となるような研究開発を行っています．今回紹介したようなの LLM と数理的な手法を組み合わせたアプローチには説明以外にも様々な応用先が考えられますので，引き続き研究を進めていきたいと思います．

参考文献

Liffiton, M. H., & Sakallah, K. A. (2008). Algorithms for computing minimal unsatisfiable subsets of constraints. Journal of Automated Reasoning, 40, 1-33.
Chen, H., Constante-Flores, G. E., & Li, C. (2024). Diagnosing infeasible optimization problems using large language models. INFOR: Information Systems and Operational Research, 62(4), 573-587.
Zhang, Y., Kang, Q., Yu, W. Y., Gong, H., Fu, X., Han, X., ... & Ma, C. (2025). Decision information meets large language models: The future of explainable operations research. arXiv preprint arXiv:2502.09994.
Vasileiou, S. L., & Yeoh, W. (2025, April). TRACE-cs: A synergistic approach to explainable course scheduling using llms and logic. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 39, No. 28, pp. 29706-29708).
Wang, L., Xu, W., Lan, Y., Hu, Z., Lan, Y., Lee, R. K. W., & Lim, E. P. (2023, July). Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (pp. 2609-2634).
Xu, B., Peng, Z., Lei, B., Mukherjee, S., Liu, Y., & Xu, D. (2023). Rewoo: Decoupling reasoning from observations for efficient augmented language models. arXiv preprint arXiv:2305.18323.

Appendix

既存のコードベースをできるだけ変更しないための工夫

この Appendix では，既存の数理最適化システムのコードベースをそのまま維持しつつ説明の仕組みを導入する上で役に立ったちょっとした実装上の工夫の話をしたいと思います．他の方が過去の記事で紹介しているようなクラスの設計に関わる話です (他の方々の記事: 1, 2, 3)．

先述の通り，MUS の計算には CPMpy を使用しています．これは，CP-SAT，Z3，Choco などの複数の solver を共通の I/F で使えるようにするモデリングツールの一種です．今回は，MUS の計算機能が欲しくて CPMpy を使っていますが，一方で既存の最適化システムはより求解が速い別の解法で実装されています．この解法は MUS や Irreducible Infeasible Set の解析機能をサポートしていません．そうなると，どのように既存の最適化システムの大工事を避けつつ説明システムを実装するかが悩みどころとなります．しかし，今回は既存の最適化システムの方で行っていたクラス設計のちょっとした工夫のお陰で既存システムの大工事を回避しつつ説明システムを後から付け加えることができました．その構成を簡略化して図示したものが図 11 となります(API サーバや UI に関わるクラスは省略しています)．

特に図中の Director と Builder が重要となります．Director が抽象化した数理最適化のスケジューリング問題の情報を持ち Builder に対してモデル構築に必要な情報を与えます．Builder は差し替え可能となっており，その具象クラスにおいて何らかの solver (例えば Gurobi や HiGHS 等)を使ってモデルを構築します．これは元々，

問題の実装を抽象化して後から他の実問題にも使い回せるようにする
具体的な解法の実装(特定の solver，自前のアルゴリズム，etc.)を後からすぐに切り替えて検証やアップデートを行えるようにする

という目的の下で採用されています．CPMpy を用いた説明システムを実装する際もこの仕組みが上手く役立ち，図 11 のように既存システムの大幅な変更を回避することができました．この話がどなたかのお役に立てば幸いです．

*1:Advent Calendar への初参加となりますのでお手柔らかにお願いします．

*2:これもある種の知的単純作業と呼べる仕事かもしれません．

*3:他の様々な説明手法については以前の記事をご参照ください．

*4:筆者が確認した範囲ではそのようなやり方をしているように見えました．もし誤っていたら申し訳ありません．

*5:実際に，我々が開発した最適化システムのコードはそうなっています

*6:もしかしたら本記事の公開時点では登場しているかもしれません...

*7:恐らくですが，LangGraph 等の他のフレームワークでも似たことはできるのではないかと思われます．

*8:Llamaindex ではQueryEngineTool や Retriever が RAG の仕組みに相当します．より詳細は，公式のドキュメントをご参照ください．

*9:今回のユースケースだとコードの実行方法や実行タイミングはこちらで制御したいため CodeAct は使用していません．

*10:恐らくですが，ほとんどの vibe coding ツールも似たような動きをしているものと思われます．今回はそれを真似しています．

*11:このチェックは LLM ではなく事前に準備したスクリプトにおいて AST や jedi を用いて機械的に行われます．

*12:図 9 の save_results は Coding Workflow のログを保存するための処理です．実行用のコードを書き出す処理ではありません．

*13:実際には，CPMpy の MUS 計算処理を少し改造したものを使っています．