「FormuEvo」を読む

要旨

一つの最適化問題には数学的に等価な複数のMIP定式化が存在し、どれを選んでも最適解は同じだが、求解にかかる計算量は桁で変わる。自然言語からMIPを自動生成するLLM研究は、意味的な正しさと実行可能性を目標にしてきたため、生成される定式化は正しくても計算上は素朴で、下流のソルバーの効率を頭打ちにする。

著者らは、定式化の設計を実行可能なモデリングプログラムの記号空間上の最適化問題として置き直し、LLMを交叉・突然変異・修復の演算子とする進化探索 FormuEvo を提案する。適合度はソルバーの実測実行時間（シフト幾何平均）である。

探索がスカラー適合度だけに頼ることを避けるため、二つの機構を足す。一つは solver-informed diagnosis で、presolve の結果・緩和の質・分枝の挙動といったソルバーの内部統計を診断LLMが言語による診断に変換し、「どこをどう直すか」の方向を与える（論文の言う verbal gradient）。もう一つは structured memory で、親子間の変更とその効果を condition / strategy / effect の三つ組に抽象化して貯め、さらに蒸留LLMが問題非依存の知識へまとめる。

Gurobi 10.0 を下流ソルバーとして TSP・JSSP・BPP・CFLP・QAP の古典問題と、ニューラルネット検証（NNV）・IMO 2025 Problem 6 の二つの新規問題で評価した。専門家が設計した定式化、既存のLLMモデリング（ORLM・StepORLM）、切除平面を進化させる EvoCut のいずれも上回り、最良ベースライン比で最大 5.5 倍の高速化を得た。

著者らの結論は、定式化の設計は静的な生成能力よりも、ソルバーの実測フィードバックで回す探索から利益を得る、というものである。

用語・記号

課題・結果・結論の対応

flowchart LR
    P1["P1<br/>正しさ優先で<br/>定式化が弱い"] --> M1["M1<br/>記号空間上の<br/>進化探索"]
    P2["P2<br/>実行時間だけでは<br/>理由が分からない"] --> M2["M2<br/>ソルバー統計の<br/>言語的診断"]
    P3["P3<br/>探索の重複と<br/>知見の使い捨て"] --> M3["M3<br/>構造化メモリと<br/>知識蒸留"]
    M1 --> R1["R1<br/>専門家設計を含む<br/>全ベースライン超え"]
    M2 --> R2["R2<br/>診断を外すと<br/>最も劣化する"]
    M3 --> R3["R3<br/>小型LLMが<br/>大型に迫る"]
    R1 --> C1["C1<br/>理論的タイト性 ≠<br/>ソルバー効率"]
    R2 --> C2["C2<br/>方向信号が<br/>探索効率を決める"]
    R3 --> C3["C3<br/>知識は問題と<br/>モデル規模を越える"]

図：三つの課題それぞれに機構を割り当て、除去実験と転移実験で個別に検証する構成になっている。

背景

MIP は製造・輸送・経営の意思決定に広く使われ、その実用性は Gurobi や COPT といったソルバーの数十年の進歩に支えられてきた。ソルバーは分枝限定法、切除平面、各種ヒューリスティクスを組み合わせ、規模と複雑さの増す問題を扱えるようにしてきた。

一方、数理計画には古くから知られた原則がある。一つの最適化問題には数学的に等価な複数のMIP定式化があり、どれも同じ最適解を保証するが、計算効率は桁で異なる。したがって実務上の解けやすさは、正しい定式化を作れたかだけでなく、構造としてソルバーが動きやすい定式化を設計できたかで決まる。

ところがこの設計は、オペレーションズ・リサーチの中でも特に専門知識を要する作業とされてきた。さらに厄介なのは、モデリングの直観が古びることである。かつて定石とされた強化制約や対称性除去が、現代ソルバーの presolve・カット生成・ヒューリスティクスと干渉し、かえって性能を落とす例が報告されている。つまり良い定式化は、ソルバーの内部実装の進歩に合わせて更新され続ける必要がある。

LLM 側の流れとしては、自然言語の問題記述から実行可能なモデリングプログラムを生成する研究が進んでいる。これらは自然言語とMIPの間の橋渡しには成功したが、目標があくまで正しさと実行可能性にあるため、出てくるのは教科書的な定式化に収束しがちである。

課題

P1：LLMモデリングは正しさを最適化しており、定式化の強さを見ていない

既存のLLMモデリングは、定式化を「充足問題」として扱う。下流ソルバーが解けて正しい解が出ればよい、という目標である。この立場では、等価な定式化の間の計算効率の差が最適化の対象にならない。著者らは加えて二点を挙げる。第一に、これらの手法はインスタンス単位で動き、個別のパラメータに縛られた定式化を出すため、問題族に対する定式化になっていない。第二に、フィードバックを持たない開ループであるため、生成物の強さを改善する機構がない。

P2：実行時間というスカラー適合度では探索がサンプル非効率になる

進化探索の一般的なボトルネックとして、適合度がスカラーであることが挙げられる。実行時間は定式化が遅いことは示すが、なぜ遅いかを示さない。緩和が弱いのか、対称性で木が膨らんでいるのか、presolve に時間を取られているのかを区別できないまま、広大な記号空間を探索することになる。

P3：長い探索での重複と、問題を越えた知見の非再利用

長い探索の中で、LLMは失敗した変更を繰り返し試したり、有効だった部分構造を忘れたりする。また、ルーティングや割当といった共通のモデリング論理は問題族をまたいで現れるのに、ある問題の探索で得た知見は次の問題に持ち越されない。

問題設定

問題 p に対するMIP定式化は、連続変数 x と整数変数 y、目的関数 c(x,y)、不等式制約 g_i(x,y) ≤ 0、等式制約 h_j(x,y) = 0 からなる。実際にはこれらを指定する実行可能なプログラム（Gurobi を呼ぶ Python コードなど）として与えられる。

F を、問題 p を符号化する意味的に正しく構文的に妥当なプログラムの集合とする。定義上、f₁, f₂ ∈ F はたとえ変数や制約の構造が違っても最適化の意味では等価であり、同じ最適解を保証する。

そのうえで著者らは、定式化設計を次の最適化問題として置き直す。

f* = argmin φ(f)   （f ∈ F）

φ(f) は下流ソルバーでの計算コスト、本論文では実行時間である。目的関数は微分不可能で、評価が高価であり、探索空間は巨大かつ離散で高度に構造化されている。この性質から、LLMを演算子とする進化探索が選ばれている。

• 入力：自然言語の問題記述と、定式化のテンプレート f₀
• 出力：問題族に対する一つの定式化（インスタンスごとではない）
• 評価：Easy インスタンス100件での SGM 実行時間を適合度とし、Medium・Hard は取り置いて最終評価に使う
• 正しさの担保：解いた目的関数値が真の最適値と一致するかを検証し、失敗した候補は修復LLMに回す。修復予算を超えた候補は捨てる

手法

中心的な着想は、ソルバーをブラックボックスの評価器ではなく、構造的なボトルネックを言葉で説明できる情報源として使うことである。

全体像

FormuEvo は世代 t で N 個の候補定式化からなる集団 P_t を保つ。五つのLLMモジュールが役割分担する。

手順は次の順に回る。

1. 初期化：問題記述とテンプレートから、生成LLMが N 個の候補を作る。局所解への早期収束を避けるため、別の変数の取り方、論理的には等価だが構造の違う制約、実装の細部の違いなど、多様な変種を出すよう促す。
2. 評価：各候補を Easy インスタンス群で実行する。コンパイルエラーや最適値の不一致があれば、エラートレースとソルバーログを修復LLMに渡す。成功した候補は SGM 実行時間を適合度として受け取る。同時に reflector LLM が、その候補のモデリング判断とソルバーの反応をメモリに抽象化する。
3. 進化：適合度上位 N 個を残す。交叉では適合度順位に応じた確率で親を2個選び、診断を経てから生成LLMが子を作る。突然変異ではエリートを1個選び、診断が指した箇所に方向づけられた改変を加える。
4. T 世代繰り返し、全世代を通じた最良の定式化を返す。

課題との対応

詳細

ソルバー内部統計の使い方

現代のMIPソルバーは、最適化の途中で presolve の結果、緩和の質、分枝の動態といった細かい統計を出力する。これらは単一の実行時間では捉えられない構造的なボトルネックを表す。論文が挙げる例では、緩和が弱いことは分数解が多く強化が要ることを示し、分枝限定木が大きいことは対称性の強い構造を示唆する。

診断LLMは、親またはエリートの定式化とそのソルバー統計を受け取り、構造化された診断を出す。診断は、主要な計算ボトルネックを特定し、それを具体的な構造的性質に帰属させ、改善の方向を提案する。論文の説明例では、親 f_i はコンパクトだが緩和が弱く分枝が過剰、親 f_j は境界は強いが presolve が高コスト、という場合に、f_j の境界強化制約を効く箇所にだけ取り込み、それ以外は f_i のコンパクトさを保つ、という指示になる。

実験設定

問題規模は Easy / Medium / Hard の三段階で、たとえば TSP は 30 / 50 / 100 都市、CFLP は 100施設200顧客 / 200施設400顧客 / 300施設600顧客である。NNV と IMO は Easy で進化させ、Hard で評価する。

ベースライン

専門家設計の定式化として、TSP では教科書的な MTZ、より強い単一品種フロー（SCF）、既知で最もタイトな緩和境界を持つ MCF-RLT までを並べ、人間の設計の到達点を追えるようにしている。LLM側は ORLM と StepORLM を、生成回数を FormuEvo と揃えて比較する。さらに EvoCut を、既存モデルへの局所的な強化と記号空間全体の探索の違いを示すために加えている。

結果

R1（P1 に対応）：専門家設計を含む全ベースラインを上回る

古典問題での Hard 設定の実行時間（SGM、秒）を、最良ベースラインと比べると次のようになる。

論文が掲げる 5.5 倍は IMO 2025 Problem 6 における最良ベースライン比である。Wins（全手法中で最速だったインスタンス数）でも、ほぼすべてのベンチマークで過半を取っている。唯一 QAP の Easy 設定だけは -0.2%（0.3936 対 0.3929）とわずかに下回る。

結果から著者らが読み取った観測が三つある。

第一に、TSP の MCF-RLT は理論上最もタイトな緩和境界を持つにもかかわらず、Hard インスタンスでは 600 秒の制限時間内に 1 問も解けていない（0/100、実行時間 600.0570）。緩和を強めるために拡張した定式化が、ソルバー側の計算を圧迫している。

第二に、ORLM と StepORLM は標準的なMILPでは正しく実行可能な定式化を出すものの、その中身は素朴な教科書定式化のままで、規模が上がると崩れる。JSSP では ORLM が全設定で制限時間に達し（0/100 solved）、QAP では正しい定式化を作れていない。NNV と IMO についても、両手法とも妥当な定式化を出せていない。

第三に、EvoCut はベースライン定式化を中程度に改善するが、下地のモデル構造に縛られる。BPP では VPSolver にも FormuEvo にも及ばない。著者らはこれを、BPP のボトルネックがLP緩和の強さではなく割当構造にあるためだと説明する。QAP では標準の二次定式化がすでに凸包にあたる Birkhoff ポリトープを定めており、強化カットによる改善余地がない。

補足として、ペアード Wilcoxon 符号付き順位検定が報告されている。TSP・CFLP・NNV・IMO では有意な改善が出る一方、BPP と QAP の Easy 設定では有意にならない（それぞれ p = 2.82E-01、4.44E-01）。著者らはこれを、小規模インスタンスはソルバーが極短時間で解いてしまい実行時間のばらつきに埋もれる「床効果」と説明し、規模が上がるほど有意になることを示している（BPP Hard で p = 2.50E-02）。

TSP で発見された定式化は、SCF の大域的な連結性保証を保ったまま、小さい持ち上げ済み DFJ 部分巡回除去カットを局所的な強化制約として選択的に組み込むものだった。

R2（P2 に対応）：診断を外すと最も劣化する

除去実験は TSP と JSSP で行われている（実行時間、SGM 秒）。

どちらの要素を外しても劣化するが、劣化幅は診断のほうが大きい。JSSP では診断を外すと全設定で最良ベースラインを下回る。

ハイパーパラメータ感度も TSP で調べられている。突然変異率は ρ = 0.3、メモリ使用率は γ = 0.7 が最良だった。γ = 1.0 が最良にならない点について著者らは、記憶を使わない生成がときどき入ることで探索の多様性が保たれ、既知のパターンへの過度な依存を防いでいると述べている。

R3（P3 に対応）：蒸留知識が小型LLMを押し上げ、性能はバックボーンに依存しない

対象問題を除く全問題から集めた蒸留知識を、小型の GPT-5.4-nano に与えた場合の進化軌跡が示されている。転移なしの GPT-5.4-nano は収束が遅く最終実行時間も高く、ベースライン定式化を超えられない。蒸留知識を与えると、収束の軌跡も最終性能も GPT-5.4-mini に近づく。

バックボーン比較では、TSP・JSSP のいずれでも GPT-5.4-mini、Claude-Sonnet-4.6、DeepSeek-V4-Flash の三つすべてが最良ベースラインを上回り、どのモデルも一貫して他を上回るわけではない。API コストは TSP でそれぞれ約 2 ドル、約 10 ドル、約 0.5 ドルである。既定に GPT-5.4-mini が選ばれているのは性能とコストの兼ね合いによる。

補遺では、Gurobi を COPT と SCIP に置き換えても一貫して改善が出ることが示されている。ただし定式化の相対的な優劣はソルバーによってかなり変わり、Gurobi 上で進化させた定式化を他ソルバーへそのまま持ち込んだ場合（FormuEvo-G）が最良とは限らない。また、進化に使っていない大規模公開ベンチマーク（TSP は Solomon の200都市、JSSP は Taillard の 100×20）でも、primal-dual ギャップの減り方がベースラインより速いことが報告されている。

結論

C1（P1・R1 に対応）

定式化の強さは、理論的な緩和のタイト性ではなく、下流ソルバーでの実測で測るべきである。MCF-RLT のように理論上最もタイトでも実務では解けない例がある以上、効率を目的関数に据えたソルバー情報つきの探索が必要になる。

C2（P2・R2 に対応）

診断機構は FormuEvo に方向信号を与える中心的な役割を果たし、記憶は探索効率を上げることで進化を助ける。両者は役割が違い、どちらを外しても性能は落ちる。

C3（P3・R3 に対応）

蒸留した知識は未知問題への zero-shot 転移と小型LLMの底上げの双方に効く。得られる利得は進化の枠組みに由来しており、特定のバックボーンLLM・モデリング言語・ソルバー実装に縛られない。

考察

著者が述べる限界と今後の課題

FormuEvo が対象にするのは、汎用MIPソルバーでそのまま解ける静的な定式化である。しかし大規模・複雑な問題では、列生成や Benders 分解のように、解いている最中に変数や制約を動的に生成する手法が使われる。こうした手法では定式化の設計と分解アルゴリズムの設計が不可分に結びついており、定式化の良し悪しは分解戦略に依存し、分解手順は定式化の構造に規定される。再定式化と分解アルゴリズムを同時に進化させる拡張は有望だが、はるかに難しい方向として今後の課題に置かれている。

この論文から読み取れること

「最大5.5倍」の内訳は見ておいたほうがよい。 5.5倍は IMO 2025 Problem 6 での最良ベースライン比であり、人間の設計知見がほとんど蓄積していない新規問題での数字である。逆に、専門家が長年磨いてきた古典問題では改善幅は小さく、最良ベースライン比で TSP Hard が約2.1倍、BPP Hard が約1.7倍、CFLP Hard が約1.3倍、JSSP Hard が約1.15倍、QAP Hard が約1.1倍である。これは弱点というより、この手法が効く場所を示していると読むほうが自然で、定式化の定石が確立していない問題ほど自動探索の取り分が大きい。

補遺 C.2 のソルバー依存性は運用上いちばん重い指摘だと思う。 「定式化の品質は本質的にソルバー依存で、あるソルバーで最良の定式化が別のソルバーでも最良とは限らない」という観測は、進化を下流ソルバーごとに回し直す必要があることを意味する。手元の環境で Gurobi と SCIP を切り替えて使う場合、探索で得た定式化の再利用可能性は自明ではない。

探索予算は小さい。 N = 8、T = 5 で毎世代8個の子なので、評価される候補は初期集団を含めても50個程度である。この規模でこれだけの改善が出ることは、探索の広さより診断が持ち込む情報量が効いているという除去実験の結果と整合的だと考える（この因果の解釈は推測）。コストが TSP で約2ドル・数時間、しかも問題族ごとに一度でよいという性質と合わせると、費用面の障壁は低い。

正しさの担保は最適値照合に依存している。 候補は「解いた目的関数値が真の最適値と一致するか」で検証される。これは真の最適値が分かる規模の学習インスタンスを用意できることを前提にしている。Easy インスタンスで進化させて Hard で評価する設計はこの前提を満たすように組まれているが、Easy 規模ですら最適性を証明できない問題族には、そのままでは適用できない。

読後に残った問い

• 進化に使う Easy インスタンス100件への過適合は、どこまで防げているのか。公開ベンチマークへの汎化は示されているが、インスタンス分布そのものが変わったときの挙動は扱われていない。
• 発見された定式化は人間が読んで理解できる形になっているのか。TSP の例（SCF ＋ 持ち上げ済み DFJ カットの選択的導入）は解釈できるが、他問題でも同じように説明がつくのかは本文からは分からない。
• 蒸留知識が「問題非依存」と言えるのは、評価した7問題の範囲でのことである。構造の大きく異なる問題族に対して、蒸留知識がむしろ誤った方向を与える場合はないのか。

付録

関連して読むもの

• 同じ「求解を速くする」目的を、定式化ではなくソルバー内部の方策学習から狙う研究として Collab-Solver がある。FormuEvo が入口（モデルの書き方）を、Collab-Solver が過程（切除平面と分岐）を扱う。
• FormuEvo は「問題族ごとに一つの定式化を進化させ、蒸留知識を問題間で転移する」構成をとる。どの問題族が構造的に近いのかを定量化する手立てとしては MILPインスタンス間の距離尺度 が対応する（両論文の間に直接の引用関係はない）。

参照箇所