LLMはOR問題の最適アルゴリズムを設計できるか？ - 金融情報システム開発なら20年以上の実績があるテンファイブ株式会社

1. はじめに：LLMはOR問題のアルゴリズムを設計できるのか

在庫をいつ、どれだけ発注するか。工場や窓口で、どの仕事を先に処理するか。店頭やECサイトに、どの商品を並べるか。こうした業務上の意思決定を数理モデルで表し、最適な答えを求める学問を オペレーションズ・リサーチ（OR：Operations Research） と呼びます。

ORの各分野では、研究者が問題ごとの数学的な構造を利用して、専用のアルゴリズムを長年かけて開発してきました。近年は、深層強化学習を使って方策（どの状態でどう行動するかのルール）を学習させる研究も盛んです。

2026年8月、ニューヨーク大学スターン経営大学院のJackie Baek氏は、論文「LLMs Can Design Near-Optimal OR Algorithms」をarXivで公開しました（2026年10月13日にv3へ更新）。この論文は、次の問いを実験で確かめています。

大規模言語モデル（LLM）は、数理的に定義されたOR問題に対して、専門家の手法に匹敵するアルゴリズムを設計できるのか。

結論から言うと、論文で最も性能の高かったモデル（gpt-5.6-sol）は、在庫管理・待ち行列ネットワークの制御・品揃え最適化という3分野のほぼすべての評価インスタンスで、元の研究で報告された最良の手法と同等以上の性能を示しました。しかも、人間が与えたのは調整していない1つのプロンプトだけです。

本記事では、まず3つのOR問題を数式で整理し、論文の実験設計と結果を解説します。次に、LLMが実際に作ったアルゴリズムの中身を数式で読み解きます。最後に、論文の限界と、筆者が考える実務への示唆を述べます。

2. 前提知識：論文で扱う3つのOR問題

2-1. 在庫管理（欠品が失われるモデル）

1つ目は、欠品した需要が失われる（後から補充できない）在庫管理問題です。たとえば、店頭に商品がなければ客は他の店で買ってしまう、という状況を表します。

毎期、ℓ期前に発注した商品が届き、新たな発注量を決め、その後に需要が発生します。ℓは発注から到着までの期間（リードタイム）です。期首の手持ち在庫をIₜ、需要をdₜ、発注量をaₜとすると、1期あたりのコストは「売れ残りの保管コスト」「欠品のペナルティ」「発注コスト」の合計です。目的は、長期的な平均コストを最小にする方策πを見つけることです。

min_{π} lim_{T \to \infty} \frac{1}{T} 𝔼 [\sum_{t = 1}^{T} h (I_{t} - d_{t})^{+} + p (d_{t} - I_{t})^{+} + c a_{t}]

ここで h は保管コスト、p は欠品ペナルティ、c は発注単価、(z)⁺ = max{z, 0} です。

この問題が難しいのは、最適な発注量が「手持ち在庫」だけでなく「発注済みでまだ届いていない商品の内訳」にも依存することです。状態は次のようなベクトルになり、リードタイムが長くなるほど状態の数が指数的に増えます。

s = (I, q_{1}, \dots, q_{ℓ - 1})

そのため、リードタイムが短い場合を除いて、動的計画法（DP：Dynamic Programming）で厳密な最適解を求めることはできません。

2-2. 待ち行列ネットワークの制御

2つ目は、複数の種類の仕事が複数のキューを流れ、少数のサーバー（作業者や機械）がどのキューを処理するかを決める問題です。工場の生産ラインや、半導体の製造工程のように、同じ設備を何度も通る工程（リエントラントライン）が典型例です。

キュー q に並ぶ仕事の数を X_q(t)、1件あたりの単位時間の保有コストを h_q とすると、目的は長期的な平均保有コストを最小にすることです。

min \underset{T \to \infty}{lim sup} \frac{1}{T} 𝔼 [\int_{0}^{T} \sum_{q = 1}^{Q} h_{q} X_{q} (t) d t]

小さなネットワークならDPで最適解を求められますが、キューの数が増えると計算できなくなります。元の研究（Dai and Gluzman, 2022）では、大きなネットワークに対して深層強化学習の手法PPO（Proximal Policy Optimization）をネットワークごとに学習させています。

2-3. 品揃え最適化（混合多項ロジットモデル）

3つ目は、どの商品の組み合わせを顧客に提示すれば期待売上が最大になるかを決める問題です。顧客がどの商品を選ぶかは、選択モデルで表します。

論文で扱う 混合多項ロジット（MMNL：Mixed Multinomial Logit）モデル では、顧客を m 個のセグメントに分けます。セグメント j の顧客は、提示された商品集合 S の中から、商品 i を次の確率で購入します。

P_{j} (i ∣ S) = \frac{u_{j i}}{v_{0 j} + \sum_{i^{'} \in S} u_{j i^{'}}}

ここで u_{ji} はセグメント j から見た商品 i の魅力度、v_{0j} は「何も買わない」選択肢の魅力度です。商品 i の価格を rᵢ、セグメント j の構成比を ω_j とすると、期待売上は次のようになります。

R (S) = \sum_{j = 1}^{m} ω_{j} \frac{\sum_{i \in S} r_{i} u_{j i}}{v_{0 j} + \sum_{i \in S} u_{j i}}

提示できる商品数には上限 k があり、|S| ≤ k の制約の下で R(S) を最大化します。この問題は、制約がなくてもNP困難（効率的な解法が知られていない問題のクラス）であることが知られています。

3. 論文の実験設計：「レベル1」と「レベル2」

3-1. 問題クラスとインスタンス

論文は、問題を次の3つ組で定式化しています。

C = (Θ, 𝒳, R)

Θ はパラメータの空間で、具体的なパラメータ θ ∈ Θ が1つの問題インスタンス（具体的な数値が入った問題）を表します。𝒳(θ) はそのインスタンスで実行可能な解の集合、R(θ, x) は解 x の報酬です。在庫管理のように行動を繰り返す問題では、解は状態から行動への写像（方策）になります。

𝒳 (θ) = {π : 𝒮 \to 𝒜}

3-2. LLMをどこで使うか：2つのレベル

論文の工夫は、LLMを使う「段階」を区別した点です。

レベル1：LLMにインスタンス θ を1つ渡し、そのインスタンス専用の解 x を返させる
レベル2：LLMに問題クラス C の説明とパラメータのおおまかな範囲だけを渡し、どのインスタンスにも使えるアルゴリズム σ（Pythonコード）を返させる

式で書くと、次のようになります。

Level 1 : x = L L M (θ) \in 𝒳 (θ) Level 2 : σ = L L M (C), x = σ (θ)

レベル2は、評価用のインスタンスを見る前にアルゴリズムを確定させる点で、本来の意味での「アルゴリズム設計」に近い設定です。なお、レベル2で返したコードの中からLLMを呼び出すことは禁止されています。これを許すと σ(θ) = LLM(θ) となり、レベル1と区別できなくなるためです。

また、論文では実験していませんが、状態ごとにLLMに行動を決めさせる「レベル0」も定義されています。LLMに直接意思決定をさせる既存研究は、このレベルに当たります。

3-3. プロンプトと計算資源

実験の条件は、意図的に単純にしてあります。

プロンプトは1つだけで、調整（プロンプトチューニング）はしない。既存の手法の名前や解き方のヒントも書かない
LLMはPythonのサンドボックス（numpy・scipyは使えるが、Gurobiなどの最適化ソルバーは使えない）で、合計3,600秒・最大50回まで計算できる
レベル2のコードは、インスタンスを受け取ってから30秒以内に解を作る必要がある
原則として、各条件で1回だけ問い合わせる（良い結果を選ぶための再試行はしない）

評価したモデルは、OpenAIのgpt-5.1、gpt-5.4、gpt-5.6-solと、Anthropicのclaude-fable-5の4つです。公開日は約8か月の範囲に収まっています。

比較対象は、ベンチマークの出典である各論文が報告した手法のうち、インスタンスごとに最も良かったものです。DPで厳密な最適解が計算できる場合は、その最適解と比較しています。

4. 主な結果：ほぼすべてのインスタンスで最良の手法と同等以上

4-1. gpt-5.6-solの結果

論文の表1から、gpt-5.6-solの主な結果を抜き出したものが次の表です。「改善率」はコストの削減率（品揃えは売上の増加率）の平均で、正の値はLLMのほうが良いことを表します。

問題クラス	比較対象	インスタンス数	レベル1の改善率	レベル2の改善率
在庫（欠品、確定的リードタイム）	厳密なDP、調整済みのcapped base stockなど	19	+1.32%	+1.27%
在庫（欠品、確率的リードタイム）	調整済みのcapped base stock	7	+1.55%	+0.60%
在庫（二重調達）	厳密なDP	6	+0.00%	−0.03%
在庫（多段階の配送）	調整済みの一定発注点方策	2	+22.78%	+11.21%
待ち行列（criss-cross、N-model）	厳密なDP	7	+0.00%	+0.00%
待ち行列（リエントラントライン）	インスタンスごとに学習したPPO	6	+5.50%	+5.00%
品揃え（MMNL、入れ子型ロジット、制約付きMMNL）	ニューラルネット＋局所探索、円錐計画など	3,393（レベル1は抽出した156）	+0.00%	+0.00%

厳密な最適解が計算できる問題では最適解と一致し、計算できない問題では既存の手法を上回るか、同等の性能でした。品揃えの改善率が0.00%なのは、比較対象がすでに最適解かそれに近い値を出しているためで、LLMはそれと一致しています。

4-2. レベル2でも性能がほとんど落ちない

注目すべきは、レベル2でもレベル1とほぼ同じ性能が出たことです。たとえば欠品型の在庫管理では、確定的リードタイム用と確率的リードタイム用の2つのアルゴリズムだけで、26のインスタンスすべてにおいて最良の手法との差が0.5%以内に収まりました。

計算にかかる手間の差も大きく、元の研究で使われた深層強化学習の手法A3Cは、ハイパーパラメータの設定1つの評価に約24 CPU時間かかり、約250通りの設定を評価していました。一方、レベル2のアルゴリズムは1回の問い合わせ（確定的リードタイムの場合、実時間598秒、そのうちサンドボックスでの計算54.9秒）で作られ、インスタンスごとの準備は平均3.0秒です。

4-3. モデルによる差と、急速な性能向上

モデルによる差もはっきり出ています。gpt-5.4はレベル1では健闘したものの、欠品型の在庫管理のレベル2では、調整済みの既存手法を一度も上回れませんでした。gpt-5.1は両方のレベルで劣っていました。claude-fable-5は、26の欠品型インスタンスのうち、レベル1で25、レベル2で23のインスタンスで最良の手法との差が0.5%以内でした。

公開時期が8か月も離れていないモデルの間でこれだけの差があることから、論文は「この能力は急速に向上している」と述べています。

5. LLMが作ったアルゴリズムの中身を数式で読む

この論文の大きな価値は、LLMが返したアルゴリズムが読めるコードであり、その仕組みを既存の手法と比べて分析できる点です。

5-1. 在庫管理：PIL制御に「不確実性の項」を加えた発注ルール

確定的リードタイムの在庫管理で、gpt-5.6-solのレベル2のアルゴリズムは、次の発注量を計算します。

q_{t}^{L L M} = min {\bar{q}, {(T - {\hat{m}}_{t} - γ \sqrt{{\hat{v}}_{t}})}^{+}}

ここで m̂ₜ と v̂ₜ は、今回の発注が届く直前に残っている在庫の平均と分散の近似値で、欠品による需要の消失を考慮しながら正規分布で近似して逐次計算します。q̄ は1回の発注量の上限、T は在庫の目標水準、γ は不確実性に対する調整の強さです。T と γ はシミュレーションで調整します。

論文は、多くの在庫方策が次の共通の形で書けると整理しています。

q_{t} = min {c, (T - P_{t})^{+}}

c は発注量の上限、Pₜ は「実質的な在庫水準」です。既存の方策とLLMの方策は、c と Pₜ の選び方だけが異なります。

方策	上限 c	実質的な在庫水準 Pₜ
基在庫方策（base stock）	q̄	Iₜ + Qₜ（手持ち在庫＋発注済みの量）
上限付き基在庫方策（capped base stock）	min{b, q̄}	Iₜ + Qₜ
予測在庫水準（PIL）制御	q̄	mₜ = E[Jₜ]（到着直前の在庫の期待値）
LLMの方策	q̄	m̂ₜ + γ√v̂ₜ

γ = 0 とすると、LLMの方策はPIL制御（van Jaarsveld and Arts, 2024）と一致します。つまり、LLMの工夫は 到着直前の在庫の標準偏差に比例する項を加えたこと です。

論文が19の設定でこの項の効果を測ったところ、標準偏差の項を加えるとすべての設定でコストが下がり、平均0.447%（95%信頼区間0.438〜0.456%）の改善でした。調整後の γ はすべての設定で負の値でした。γ が負なら、到着直前の在庫の予測がばらつくほど発注量が増えます。つまり、この項は不確実性に応じた安全在庫として働いています。

なお、PIL制御は元のベンチマーク論文の比較対象には含まれていませんでした。LLMが既存の手法を上回った理由の一部は、文献にはあるが比較されていなかった考え方を使ったことにある、と論文自身が認めています。

5-2. 待ち行列：重み付き最大圧力方策の変形

リエントラントラインの制御で、gpt-5.6-solのレベル2のアルゴリズムは、空でない各キュー q に次のスコアを付け、各ステーションでスコアが最大のキューを処理します。

S_{q} (X) = μ_{q} (w_{q} X_{q} - γ w_{r (q)} X_{r (q)}) + B_{q}

μ_q はキュー q の処理速度、r(q) は処理後に仕事が移る次のキュー、w_q は重み、B_q は定数のボーナス、γ は次のキューを割り引く係数です。このスコアは「自分のキューが長いほど優先するが、処理した結果、次のキューがすでに混んでいるなら優先度を下げる」という考え方を表しています。

これは、待ち行列理論で知られる 最大圧力方策（maximum pressure policy） の変形です。基本的な最大圧力方策は、次のスコアを使います。

μ_{q} (X_{q} - X_{r (q)})

LLMの方策は、w_q = 1、B_q = 0、γ = 1 とすると、この基本形になります（論文によると、ほかに違うのはスコアがすべて負のときに処理をしないことを許すかどうかの点だけです）。さらに、Dai and Lin（2005）が提案した重み付き最大圧力方策と比べると、違いは次のキューを γ で割り引くかどうかと、処理をしない（アイドリングする）ことを許すかどうかの2点だけです。

論文が重みとボーナスを連続的に調整して比較したところ、重み付きの各変形の平均コストの差は最大0.25%でした。つまり、この問題では LLMの方策は既存の方策の系統とほぼ同じ性能 で、性能面での新しさはありませんでした。

5-3. 品揃え最適化：手法を組み合わせたソルバー

品揃え最適化では、LLMが返したのは方策ではなく、インスタンスを受け取って商品集合を返す「ソルバー」です。gpt-5.6-solのMMNL用ソルバーは、小さな問題は全探索で厳密に解き、それ以外は貪欲法、ランダムな初期解、連続緩和などで候補を作り、商品の追加・削除・入れ替えによる局所探索で改善します。

論文はこれを「緩和する、丸める、修復する、局所的に改善する、ときどき小さな厳密問題を解く」という、ORの標準的な部品の組み合わせだと説明しています。

6. 結果は偶然ではないか：頑健性のチェック

6-1. 計算資源をゼロにした場合

サンドボックスでの計算を禁止し、考えるだけでコードを書かせた場合も検証しています。レベル2では、在庫管理と品揃えで強い性能が維持されました。確定的リードタイムの在庫管理では、計算なしで作ったアルゴリズムが6つすべてのリードタイムで最良の既存手法を上回り、計算ありの場合との差も0.4ポイント以内でした。

一方、レベル1の在庫管理では、多くの場合に単純な公式に頼るようになり、既存手法を下回りました。待ち行列でも、N-modelとリエントラントラインでは性能が落ちています。

6-2. 新しいインスタンスへの汎化

学習データにベンチマークの答えが含まれていた（データ汚染の）可能性を確かめるため、レベル2のコードをそのまま使い、元のベンチマークにない新しいパラメータのインスタンスでも評価しています。gpt-5.6-solは、在庫管理の新しいインスタンスすべてで最良の既存手法を上回りました。claude-fable-5は、確率的リードタイムではすべて、確定的リードタイムでは30中13のインスタンスで上回りました。

6-3. 同じ問い合わせを繰り返した場合

同じプロンプトでgpt-5.6-solに繰り返し問い合わせた結果、有効なアルゴリズムの性能は多くの問題で狭い範囲に収まりました。たとえば欠品型の在庫管理では、問題クラスごとの平均の差が1.3ポイント未満でした。一方、多段階の配送では6.8ポイントの差があり、100回のうち3回は有効な結果を出せない不良なコードでした（すべて品揃えの問題）。

7. 論文に対する評価と限界

7-1. MMNLのベンチマークは見かけより易しかった

論文自身が重要な注意点として挙げているのが、MMNLのベンチマークの構造です。公開されている628のMMNLインスタンスには、商品の魅力度のベクトルが2種類しかありませんでした。この構造に気付けば、各種類の中で価格順に並べ、それぞれから何個選ぶかを全探索するだけで厳密な最適解が求まります。

LLMがこの構造をヒントなしで利用できたことは興味深いですが、一般のMMNL問題を解けることを示したわけではありません。論文は追加で、魅力度が連続的に分布するインスタンスでも評価していますが、そのインスタンスも単純な局所探索で解ける程度の難しさだったと述べています。

7-2. 比較対象は元の論文の手法に限られる

比較対象は、ベンチマークの出典である論文が評価した手法です。論文は「文献にあるすべての手法に勝つとは主張しない」と明記しています。前述のPIL制御のように、比較対象に含まれていなかった既存の手法をLLMが使っていた例もあります。

7-3. 学習データの影響は完全には否定できない

LLMが学習の段階でベンチマークの問題や答えを見ていた可能性は、完全には否定できません。新しいインスタンスでの評価はこの懸念を部分的に和らげますが、決定的な証拠ではないと論文自身も述べています。

7-4. 問題クラスの定義に結果が左右される

待ち行列の実験では、ネットワークの構造を指定したクラスとは別に、任意の待ち行列ネットワークを含む広いクラスでもレベル2を試しています。その結果、LLMは汎用的なルールを返し、リエントラントラインでは健闘したものの、criss-crossとN-modelでは大きく性能が落ちました。問題クラスを広く取りすぎると、もっともらしいが特定の構造に弱い汎用的な解法が返ってくることがわかります。

7-5. 新しい原理の発見ではなく、理論的な保証もない

論文の事例分析が示すとおり、LLMは既存のアイデアを問題に合わせて組み合わせ、調整したのであって、新しいアルゴリズムの原理を発見したわけではありません。また、結果はすべて実験によるもので、近似精度の理論的な保証はありません。

加えて、本論文は単著のプレプリントで、arXivのページには学術誌への掲載情報は記載されていません（2026年10月時点）。

8. 筆者の考察：アルゴリズム設計が安くなった世界で何が変わるか

ここからは、論文の内容を踏まえた筆者の考えです。

8-1. 価値は「解く」から「定式化する」「検証する」へ移る

この論文が示しているのは、問題が数式で正しく定義されていれば、アルゴリズム設計の大部分をLLMに任せられる段階に来ている ということです。論文は、問題の定式化やデータの準備を意図的に実験から外しています。逆に言えば、実務でLLMの力を引き出せるかどうかは、人間が問題を正しく定式化できるかどうかにかかっています。

金融システムの開発でも同じことが言えます。たとえば、ATMの現金補充計画は在庫管理問題、コールセンターの人員配置は待ち行列の問題、金融商品のおすすめ表示は品揃え最適化の問題として定式化できます。これらの業務の制約やコストを正しく数式に落とし込める人材の価値は、今後さらに高まると考えます。

8-2. 「読めるコードで返ってくる」ことの価値

筆者が実務上最も重要だと考えるのは、レベル2の成果物が 人間が読めるコード だという点です。深層強化学習で作った方策は、なぜその行動を選んだのかを説明するのが困難です。一方、LLMが返したアルゴリズムは、本記事の5章で見たように数式で表し、既存の理論と比べて検証できます。

監査や説明責任が厳しく求められる金融業界では、この違いは決定的です。「なぜこの発注量なのか」「なぜこの処理順なのか」を、コードと数式で説明できるからです。

8-3. 「問題クラスの切り方」が新しい設計スキルになる

7-4で見たように、問題クラスを広く定義しすぎると、LLMは汎用的で弱いルールを返しました。これは、LLMに仕事を頼むときの重要な教訓です。

「最適化アルゴリズムを作って」と漠然と頼むのではなく、「このネットワーク構造で、このパラメータの範囲で」と問題の構造を具体的に指定するほど、LLMは適切な手法を選べます。システム設計で要件を明確にするのと同じように、LLMに渡す問題の範囲を適切に切り出すこと が、これからのエンジニアに求められる設計スキルになると考えます。

8-4. 実務で使うときの確認事項

LLMにアルゴリズムを設計させる場合、筆者は少なくとも次の確認が必要だと考えます。

厳密解が計算できる小さな問題で、LLMのアルゴリズムが最適解を再現できるかを確かめる
既知の標準的な手法（基在庫方策やcμルールなど）と同じ条件で比較する
設計時に使っていない新しいインスタンスで性能を評価する
同じ依頼を複数回行い、結果のばらつきと不良なコードの発生率を確認する
返されたコードを人間がレビューし、数式としてどのような方策なのかを説明できるようにしてから本番で使う

論文の実験手順そのものが、LLMに作らせたアルゴリズムを検証する手順の良い手本になっています。

9. まとめ：LLMはOR研究の「強力なベースライン」になった

本論文は、在庫管理、待ち行列ネットワークの制御、品揃え最適化という3つのOR問題で、LLMが専門家の手法に匹敵するアルゴリズムを設計できることを示しました。

最も性能の高いモデルは、ほぼすべてのインスタンスで、元の研究の最良の手法と同等以上の性能を示した
問題クラスの説明だけから作ったレベル2のアルゴリズムでも、性能はほとんど落ちなかった
LLMの方策は、PIL制御や最大圧力方策など、既存の手法を問題に合わせて組み合わせ、調整したものだった
公開時期が8か月以内のモデルの間でも性能差が大きく、能力は急速に向上している

一方で、ベンチマークの構造による易しさ、比較対象の範囲、学習データの影響、問題クラスの定義への依存といった限界もあります。

論文の結論にあるとおり、少なくとも数理的に定義されたOR問題では、最先端のLLMはアルゴリズム設計の 真剣に比較すべきベースライン になったといえます。これからのORの研究や実務では、「LLMに1回頼んだ結果より良いか」が、新しい手法の価値を測る基準の一つになるかもしれません。

参考文献・関連研究

Baek, J. (2026). LLMs Can Design Near-Optimal OR Algorithms. arXiv:2608.27296.
Gijsbrechts, J., Boute, R. N., Van Mieghem, J. A., & Zhang, D. J. (2022). Can Deep Reinforcement Learning Improve Inventory Management? Performance on Lost Sales, Dual-Sourcing, and Multi-Echelon Problems. Manufacturing & Service Operations Management, 24(3), 1349–1368.
Dai, J. G., & Gluzman, M. (2022). Queueing Network Controls via Deep Reinforcement Learning. Stochastic Systems, 12(1), 30–67.
Dai, J. G., & Lin, W. (2005). Maximum Pressure Policies in Stochastic Processing Networks. Operations Research, 53(2), 197–218.
van Jaarsveld, W., & Arts, J. (2024). Projected Inventory-Level Policies for Lost Sales Inventory Systems: Asymptotic Optimality in Two Regimes. Operations Research, 72(5), 1790–1805.
Guo, Q., Lagzi, S., Wang, C., Chen, N., Gallego, G., Kunnumkal, S., Wang, Y., & Yu, L. (2025). Solving assortment optimization with first-order methods and neural networks: A computational framework and public benchmark. SSRN.

本記事は2026年10月時点で公開されている文献・情報に基づく解説です。論文の主張と、筆者による整理・考察を区別して記載しています。数式の記号は、読みやすさのために論文から一部簡略化しています。