技術概要：OPT-Engine 最適化モデリングにおける LLM の限界を複雑性スケーリングを通じてベンチマーク化

1. 問題提起

大規模言語モデル（LLM）は、自然言語の解釈や最適化のための数学モデルの生成において有望な能力を示しているが、現実世界のオペレーションズリサーチ（OR）への応用は依然として脆い。既存のベンチマークは、静的で固定規模のインスタンスや教科書的な問題に依存しており、産業応用に見られる組み合わせ的複雑性や構造的密度を捉えきれていない。さらに、競争数学における LLM の成功と、特に問題規模が増大するにつれて複雑な最適化問題の定式化および解決能力との間には、大きな性能格差が存在する。コミュニティには、自動化された問題定式化の限界を体系的に探求し、制御された複雑性スケーリング下で異なる推論パラダイム（純粋テキスト推論対ソルバー統合推論）の有効性を区別するための、厳密かつ拡張可能なフレームワークが欠けている。

2. 手法：OPT-Engine フレームワーク

これらのギャップに対処するため、著者らは、定量化可能かつ制御可能な複雑性を持つ問題インスタンスを生成するように設計された拡張可能なベンチマークフレームワークであるOPT-Engineを導入する。

2.1. ベンチマーク分類

OPT-Engine は、2 つの階層に分類された 10 の標準的な OR 問題クラスを網羅する。

• 線形計画法（LP）： 在庫、ポートフォリオ配分、生産、輸送、および汚染管理の問題。
• 混合整数計画法（MIP）： 巡回セールスマン問題（TSP）、ナップサック問題、ビンパッキング、ジョブショップスケジューリング、および最小費用ネットワークフロー。

2.2. スケーラブルな生成パイプライン

このフレームワークは、検証可能な問題インスタンスを生成するための 4 段階のパイプラインを採用する。

1. 数値インスタンス生成： 生成器 $G$ が、問題クラスと難易度制御ベクトル $\theta$（例：TSP における都市数 $N_{cities}$）を数値インスタンスにマッピングする。重要なことに、この段階では、真の最適解と目的関数値を計算するためにソルバーテンプレートを利用する。
2. 標準問題の構築： 数値インスタンスは、構造化テンプレートを用いて、形式的で標準的な問題記述 $s_c$ にマッピングされる。
3. 問題拡張： 専用の LLM エージェントが、標準的な記述を多様で文脈に富んだ自然言語の物語（$s_r$）に言い換え、基礎となる数学的構造を保持しつつ現実的なシナリオをシミュレートする。
4. インスタンス検証： LLM を審判役とした検証モジュールとルールベースの検証器を組み合わせることで、言い換えられた物語が、真の値との構造的同等性と数値的一貫性を維持していることを保証する。

2.3. 評価パラダイム

このフレームワークは、2 つの主要な推論アプローチを評価する。

• 純粋テキスト推論（PTR）： LLM は外部ツールなしで、チェーン・オブ・ Thought（CoT）を使用してエンドツーエンドで解を推論する。
• ソルバー統合推論（SIR）： LLM は問題を実行可能なコード（例：Gurobi/COPT）に変換し、それを外部の決定論的ソルバーで解く。
• 計算 PTR（CompPTR）： LLM が局所計算のために Python プリミティブを使用するが、グローバル最適化ソルバーの呼び出しは制限される中間アプローチ。

3. 主要な結果

3.1. スケーリングとロバスト性

• SIR の優位性： 問題の複雑性がスケーリング（次元と制約の増加）するにつれて、SIR は高い精度を維持するか、わずかな劣化しか示さない。対照的に、PTR は決定的なロバスト性の欠如を示し、問題サイズが増大するにつれて性能が劇的に崩壊する。
• モデル規模の影響： 小規模モデル（例：Qwen3-4B）は、SIR におけるコード生成の失敗により低複雑性では SIR よりも優れた性能を示す可能性があるが、この優位性は一時的である。検証可能な報酬からの強化学習（RLVR）を用いてコード生成を改善することで、SIR はすべての次元において PTR を一貫して上回る。

3.2. 機械的な失敗モード

• 算術対構造： 誤差分解により、PTR の失敗は二面的であることが明らかになった。複雑性が増大するにつれて、モデルはまずグローバルな論理制約を満たすことに失敗し（実行可能性の崩壊）、その後、数値的な精度を達成することに失敗する。
• 計算支援の限界： CompPTR（PTR に Python ツールを追加）は算術誤差を軽減し局所的な実行可能性を改善するが、グローバルな最適化制約を強制することはできない。モデルは全体的な組み合わせ的依存関係を内部化できず、高スケーリングでは標準的な PTR と同様の性能低下を招く。

3.3. ボトルネックの診断

著者らは、失敗の主要な原因を特定するための診断実験を実施した。

• 言語的複雑性： 問題記述のパープレキシティ（PPL）を変化させても、精度への影響は無視できた。
• 目的関数の摂動： 目的関数に定数シフトを加えても、性能は著しく低下しなかった。
• 制約の拡張： 数学的に単純な追加制約（例：「2 つの道路のうちのちょうど 1 つが含まれなければならない」）の導入は、すべての問題クラスおよびパラダイムにおいて、大幅かつ一貫した精度の低下を引き起こした。

ボトルネックに関する結論： 最適化における現在の最先端 LLM の主要なボトルネックは、言語理解や目的関数の定式化ではなく、制約の自動化された定式化である。モデルは、教科書的な定式化を超えて一般化できず、現実の応用で見られる豊かで制約の多いバリエーションに対処することに苦労している。

4. 貢献

1. OPT-Engine フレームワーク： 最適化モデリングにおける LLM の評価のために、数学的構造と言語に対する微細でスケーラブルな制御を可能にする包括的かつ拡張可能なベンチマーク。
2. パラダイム評価： PTR はスケーリングにおいてロバスト性を欠き、SIR は高複雑性シナリオにおいて精度を維持するために不可欠であることを示す実証的証拠。
3. ツール統合分析： 外部計算ツールが局所計算を支援するが、ソルバー統合なしでは LLM がグローバルな最適化制約を遵守する根本的な能力の欠如を解決しないという知見。
4. ボトルネックの特定： 問題理解や目的摂動とは区別し、制約定式化を主要な失敗点として特定すること。

5. 意義と主張

本論文は、OPT-Engine が、孤立した実証や静的データセット上の並列比較を超えて分野を進展させるために必要な診断的厳密性を提供すると主張している。複雑性スケーリングのプロトコルを確立することにより、このフレームワークは、現在の LLM が標準的な訓練データからのパターンに大きく依存しており、新しい制約の組み合わせについてロバストに推論できないことを明らかにしている。

著者らは、これらの知見が現在のパラダイムの限界を明確にし、次世代 LLM の開発のための構造化されたロードマップを提供すると主張している。彼らは、最適化モデリングが産業環境で実用可能になるためには、モデルは「推論の幻想」を超え、制約定式化において忠実性を達成する必要があると強調している。本論文は、正確な解（LP/MIP）に焦点を当てているが、将来の研究は NP 困難問題に対するヒューリスティックを探求し、フレームワークを非線形および確率的ドメインに拡張すべきであると結論付けている。この将来の研究を促進するため、コードとデータは公開されている。