「Collab-Solver」を読む

要旨

MILP ソルバーは分枝限定法の上に presolve、切除平面の生成と選択、ノード選択、分岐といったモジュールを積み重ねて動く。機械学習でこれらのヒューリスティクスを置き換える研究は成果を上げてきたが、そのほとんどはモジュールを一つずつ独立に学習させている。

しかし分枝カット法では、モジュールは順番に依存している。切除平面の選択はLP緩和を変えるため、下流の分岐方策が出会う観測や候補変数まで変えてしまう。独立に学習した方策は配備時に食い違い（deployment mismatch）を起こし、同時に更新すれば互いの環境を変え合って非定常になる。

著者らは、切除平面選択をリーダー、分岐をフォロワーとするシュタッケルベルグ・ゲームとして両者の相互作用を定式化し、二段階の学習手順 Collab-Solver を提案する。第一段階は「データ連絡つき事前学習」で、学習済みの切除平面方策が作る状態の上で分岐方策を学習させる。第二段階は「並行ジョイント微調整」で、リーダーを遅く・フォロワーを速く更新する二時間尺度の更新則によって非定常性を抑える。

SCIP 8.0 を土台に6つのMILPベンチマーク（合成5＋実世界1）で評価し、求解時間と primal-dual 積分の両方でベースラインを上回った。学習時とは変数数・制約数が大きく異なるテスト集合でも SCIP 比で約50%の時間短縮を保ち、さらに predict-and-search を上位に加えた三モジュール階層への拡張も示した。

用語・記号

課題・結果・結論の対応

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/>6ベンチで時間・<br/>PD積分とも改善"]
    M2 --> R1
    M3 --> R2["R2<br/>規模汎化と<br/>三モジュール拡張"]
    R1 --> C1["C1<br/>依存の明示が<br/>協調を生む"]
    R2 --> C2["C2<br/>多モジュールへ<br/>一般化できる"]

図：P1 と P2 はどちらも「モジュール間の依存を扱えていない」ことに帰着し、シュタッケルベルグ・ゲームという一つの定式化から出る二段階の学習手順で別々に潰される。P3 はその枠組みの一般性を問う。

背景

MILP は線形の目的関数と線形制約のもとで一部または全部の変数を整数に制限する問題で、大半のインスタンスが NP 困難である。SCIP、CPLEX、Gurobi といった現代ソルバーは分枝限定法を土台に、密に結合した複数のアルゴリズムモジュールを組み合わせて探索空間を効率よく調べる。

分枝カット法での流れは次のようになる。整数制約を落としたLP緩和を解くと双対限界が得られる。切除平面は、整数実行可能解を除かずにこの緩和を締める線形不等式で、連続するラウンドで追加される。各ラウンドは (i) 現在のLP緩和を解く、(ii) 候補カットの集合を生成する、(iii) その部分集合を選んで緩和に足す、の三段からなる。第三段が切除平面選択で、どの制約が入るかを直接決めるため、双対限界の締まり方を左右する。

一方、LP緩和の最適解が整数性を破る場合、その葉ノードに x_i ≤ ⌊x_i*⌋ または x_i ≥ ⌈x_i*⌉ を足して二つの部分問題に分ける。この変数 x_i を選ぶのが分岐である。分枝カット法では両者が交互に現れ、強く相関している。

従来は各モジュールのヒューリスティクスを人手で設計してきたが、多大な労力を要し、新しい問題領域へ移すと頑健性を欠く。そこで分岐、ノード選択、切除平面選択を学習で置き換える研究が進んだ。代表例として、切除平面側では階層構造を持つ HEM、分岐側ではGCNNで方策をパラメータ化する learning to branch がある。

課題

P1：独立に学習した方策は、配備時に食い違う

既存研究は各モジュールの方策を個別に学習させ、相互依存を明示的にモデル化していない。しかし分枝カット法では、切除平面の選択がLP緩和を変え、それによって下流の分岐方策が出会う観測と候補変数が変わる。したがって、既定のヒューリスティクスのもとで集めたデータで学習した分岐方策を、学習済みの切除平面方策と組み合わせて配備すると、学習時と配備時で状態分布がずれる。

著者らはこれを具体的な観測でも裏づけている。HEM（切除平面）と GCNN-B（分岐）の優劣はデータセットごとに入れ替わり、あるデータセットは切除平面方策に、別のデータセットは分岐方策に依存している。単に学習済みモジュールを並べるだけでは、この両面を取り込めない。

P2：同時に更新すると非定常になる

では両方を同時に学習すればよいかというと、そこには別の問題がある。一方の方策が変われば他方にとっての環境が変わるため、学習問題が非定常になる。単純な同時更新は不安定を招き、性能を落とすこともある。

P3：二モジュールで閉じた話なのか

切除平面と分岐は分枝カット法の中でも特に結合が強い組み合わせだが、ソルバーには主ヒューリスティクスや presolve など他のモジュールもある。提案する定式化がこの二つに固有のものなのか、より多くのモジュールへ広がるのかは、それ自体が検証すべき点になる。

問題設定

切除平面モジュールと分岐モジュールを、それぞれカットエージェントと分岐エージェントという二つのエージェントとして扱う。求解過程を有限ホライズンの部分観測マルコフゲーム G = (S, A_c, A_b, P, O_c, O_b, r) として置く。

• カットエージェントはカット関連の特徴 o_c ∈ O_c を観測する
• 分岐エージェントは MILP インスタンスの特徴 o_b ∈ O_b を二部グラフとして観測する
• 各決定ステップで、カットエージェントは (o_c, o_b) に基づいて生成済みカットの部分集合 a_c を選び、現在のLP緩和を更新する
• その結果のLP解が整数性を破るなら、分岐エージェントが o_b に基づいて分岐変数を選ぶ
• 状態は P(s' | s, a_c, a_b) に従って遷移し、両エージェントが新しい観測と報酬を受け取る

分岐の決定が切除平面選択の結果に依存するので、カットエージェントをリーダー、分岐エージェントをフォロワーとする。協調学習の目的は次の二段最適化になる。

min  T_D(π_c, π_b*)
π_c
s.t. π_b* ∈ argmin T_D(π_c, π_b)
                π_b

T_D(π_c, π_b) は学習データ D 上の累積報酬の期待値である。報酬は標準設定では求解時間の符号反転を使う。求解時間が情報にならないほど難しいインスタンスでは、解の品質を反映させるために PD gap を報酬に使う。難易度は学習データの一部で平均求解時間を測って判定する。

手法

中心的な着想は、モジュール間の順序依存をリーダー・フォロワー関係として明示し、データの作り方と更新の速さの両方でその順序を尊重することである。

M2：データ連絡つき事前学習

第一段階では、学習済みの π_c が誘導する状態の上で π_b を事前学習し、配備時の食い違いを減らす。

切除平面方策の事前学習。 HEM に着想を得て、まず方策勾配法で π_c を学習する。HEM と違うのは、入力に候補カット特徴 o_c だけでなく MILP 特徴 o_b も入れる点である。o_b が二つの方策をつなぐ連絡路になるため、方策は π_c(a_c | o_c ∘ o_b) の形をとる。∘ は単なる連結ではなく、両者を別の入口からネットワークへ入れることを表す。

ネットワークは次の構成をとる。

π_c のパラメータ θ は方策勾配で最適化する。この段階では π_b はまだ学習されておらず、SCIP の既定の分岐が使われる。報酬は求解が終わったときにだけ非ゼロで与える。

分岐方策の事前学習。 π_c を学習したあと、SCIP の切除平面ヒューリスティクスを π_c で置き換え、分岐には強分岐を使って教師データ D_e = {(o_b, a_b)} を作る。ここでのデータ連絡は暗黙的に働く。π_c が選んだカットは制約として現在のMILPに追加されるため、π_c の行動は二部グラフ o_b の中に織り込まれる。つまり教師データ D_e は最初から π_c に条件づけられている。

強分岐は最小の木を作る一方で計算コストが高いので、D_e を使って行動クローニング損失で π_b を学習し、ニューラルネットの推論速度で同等の分岐を得る。π_b のネットワークは GCNN に MLP を重ねた構成で、先行研究の learning to branch と同様である。

SCIP を土台に選んだ理由は、オープンソースで改変しやすいためである。Gurobi や CPLEX は切除平面選択と分岐の公開APIを持たない。

M3：二時間尺度の並行ジョイント微調整

事前学習した π_c と π_b を使って一つのインスタンスを解き、得られたデータで両方策を並行して最適化する。ただし単純な同時更新は非定常を招くため、更新頻度を分ける。

• 遅い時間尺度：リーダー π_c を ω_c インスタンスごとに一度更新する。リーダーは分岐対象となるノードを生み出す生成器とみなせ、ゲームへの影響が大きいので、ゆっくり動かす。
• 速い時間尺度：フォロワー π_b を ω_b インスタンスごとに一度更新する（ω_b < ω_c）。

この段階では方策が更新され続けるため、π_b のオフライン模倣学習はもう使えない。代わりに、ε-greedy 探索のもとで (π_c, π_b) が生成した軌跡を使い、方策勾配で π_b を微調整する。π_c の微調整方法は第一段階と同じだが、今度は π_b も軌跡の生成に参加する。実験では ω_c = 4、ω_b = 1 を使っている。

課題との対応

詳細

データ・対象

6つのMILPベンチマークを使う。Set Covering、Maximum Independent Set、Combinatorial Auction、Capacitated Facility Location、Mixed Integer Knapsack、Production Planning で、最後の Production Planning だけが実世界データである。Capacitated Facility Location、Mixed Integer Knapsack、Production Planning は整数変数と連続変数の両方を含み、残りは二値線形計画である。

合成データは学習10000件・検証2000件・テスト100件、実世界データは 80% / 10% / 10% で分割する。微調整用データは学習集合から一様再サンプリングした少量である。異種問題間の汎化は本論文の狙いではないため、データセットごとに別のモデルを学習する。

実験・評価条件

• 土台ソルバー：SCIP 8.0。presolve や主ヒューリスティクスなど高度な機能はすべて有効にし、実運用に近い設定にする
• 制限時間：300秒
• 評価指標：平均求解時間（Time）と平均 primal-dual 積分（PD 積分）。どちらも小さいほど良い。PD 積分は主限界と双対限界の曲線に挟まれた面積で、制限時間内に解ききれないデータセットでは解の最適性を反映するためこちらが重要になる
• 各実験は5個の乱数シードで実行し、平均と標準偏差を報告する
• ベースライン：既定パラメータの SCIP、ベイズ最適化によるハイパーパラメータ調整の SMAC3、切除平面学習の HEM、模倣学習による分岐の GCNN-B、強化学習による分岐の RL-B

商用ソルバーを土台に使わない理由は、切除平面選択と分岐のAPIが公開されていないことに加え、SCIP が商用ソルバーより遅いため直接比較が不公平になることである。

結果

R1（P1・P2 に対応）：6ベンチマークで時間・PD 積分とも改善

主結果（求解時間（秒）／ PD 積分、平均±標準偏差）。

著者らが読み取った観測は次のとおりである。

易しい3データセット（上段）では、SCIP に対して時間指標でほぼ60%の改善を達成している。改善幅は難しい下段でより顕著で、難しいインスタンスほどモジュール間の協調が重要になることを示す。実世界の Production Planning ではテスト10件中3件が制限時間300秒に達しているため、このデータセットでは PD 積分のほうが重要になる。

HEM と GCNN-B はほとんどのデータセットで既定 SCIP を上回るが、優劣はデータセットごとに入れ替わる。これは、あるデータセットの求解が切除平面方策に依存し、別のデータセットは分岐方策に依存することを意味する。Collab-Solver はその両面を取り込める。

SMAC3 はほとんどのデータセットで既定 SCIP を上回るが、Set Covering では既定を超えるハイパーパラメータを見つけられなかった。既定値が人間の設計知識で調整済みだからだと著者らは説明する。RL-B は概ね既定 SCIP を上回らず、標準偏差も大きい。専門家データからの知識を欠くことと、RL 特有の不安定さによるものとされる。

長時間設定。 NeurIPS ML4CO コンペの Item Placement（IP）データセットで、制限時間1000秒での PD gap を比較している。SCIP 16.57±4.71、SMAC3 12.91±3.53、HEM 14.58±4.26、GCNN-B 15.47±4.09、RL-B 16.10±9.78 に対し、Collab-Solver は 10.32±2.83 である。この極端に難しいデータセットでは GCNN-B（分岐）が HEM（切除平面）よりわずかに悪く、カットの役割が大きいことを示している。

除去実験。 微調整を外した版（w/o F）と、微調整とデータ連絡の両方を外した版（w/o F&Comm）を比較する。後者は先行するマルチエージェント手法におおむね対応する。

w/o F&Comm と w/o F の差が第一段階のデータ連絡の寄与、w/o F と完全版の差が安定化した微調整の寄与にあたる。どちらも一貫して改善に寄与している。

R2（P3 に対応）：規模を変えても汎化する

学習集合と変数数 n・制約数 m が大きく異なるテスト集合を作って評価している。たとえば Capacitated Facility Location は学習時の (n, m) = (10100, 10203) に対しテストは (20100, 20303) である。

学習集合とテスト集合の差が大きいにもかかわらず、Collab-Solver が最も強い汎化を示し、SCIP に対して約50%の時間短縮を達成している。

R3（P3 に対応）：三モジュール階層への拡張

PnS を上流の主ヒューリスティクスエージェントとして加えると、PnS が探索空間を制限し、切除平面が結果のLP緩和を締め、分岐が探索木を調べる、という三層の依存が自然にできる。PnS は求解前に二値変数の 7.5% を 1 に、7.5% を 0 に固定し、その分だけ定式化の規模が (n, m) = (100471, 140605) から (107554, 154753) へ増える。

PnS を階層シュタッケルベルグ・ゲームの超リーダーとして定式化し、対照学習で事前学習したうえで切除平面方策と協調させ、最後に分岐方策を加える。大規模な Unit Commitment で、Gurobi と SCIP の双方に3600秒の制限を課し、Gurobi の最良実行可能解を下界として、目的関数値がその101%に達した時点で解けたとみなす。

SCIP 比で求解時間を約26%短縮し、Solved Ratio を 57% から 71% へ引き上げている。テスト7件のうち5件を解き、他手法はいずれも4件だった。著者らはこれを三モジュール階層協調の概念実証と位置づけている。

結論

C1（P1・P2・R1 に対応）

独立に学習したソルバーモジュールは、協調の観点では最適でない振る舞いをしうる。リーダー・フォロワーの相互作用を明示的にモデル化すると、より効果的な協調が得られる。またジョイント最適化を非定常学習問題として捉え、二時間尺度の更新則を用いることで、並行学習が安定する。

C2（P3・R2・R3 に対応）

この枠組みは二モジュールに限らず、階層シュタッケルベルグ・ゲームとして多モジュールへ一般化できる。学習済み方策は、学習時と規模の大きく異なるインスタンス集合に対しても優れた汎化を示す。

考察

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

Collab-Solver は現在、問題クラスごとに別のモデルを学習している。異種問題間の汎化は本論文の狙いではないと明言されており、クロスクラスの汎化を改善するマルチタスク学習が今後の課題として挙げられている。

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

「マルチエージェント強化学習」と一言でまとめると中身を取り違える。 学習の中身は均質ではない。切除平面方策 π_c は最初から方策勾配（強化学習）で学ぶが、分岐方策 π_b は強分岐を教師とする行動クローニング、つまり模倣学習で事前学習される。方策勾配に切り替わるのは第二段階の微調整からである。RL-B（純粋な強化学習の分岐）が既定 SCIP をほとんど上回れず標準偏差も大きかったという結果を見ると、この「模倣で土台を作ってから強化学習で仕上げる」構成は偶然ではなく、意図的な設計だと読める。

データ連絡は仕掛けとしては地味だが、効き方は大きい。 π_c が選んだカットは制約としてMILPに追加され、その結果が二部グラフ o_b に自動的に反映される。だから明示的な通信チャネルを作らなくても、π_c の行動は π_b の観測に織り込まれている。除去実験の Max Independent Set で 4.58s → 2.70s と、微調整（2.70s → 1.41s）に匹敵する改善が出ているのは、この「暗黙の連絡」だけで学習時と配備時のずれが相当に埋まることを意味する。実装コストの割に取り分が大きい部分だと思う。

「リーダーを遅く」の向きは直感と逆かもしれない。 二時間尺度では ω_c = 4、ω_b = 1 なので、リーダーである切除平面方策のほうが更新頻度が低い。理由は論文の説明どおり、リーダーが分岐対象のノードを生み出す生成器であり、ゲームへの影響が大きいからである。フォロワーが先に新しい環境に追随し、そのうえでリーダーが動く、という順序になっている。

比較の土台が SCIP であることは、実務上の読み替えが要る。 商用ソルバーが切除平面選択と分岐のAPIを公開していないという事情から、SCIP 上でしか検証できていない。SCIP 比で 50〜60% の短縮が出たとしても、Gurobi や CPLEX の既定設定と比べてどの位置にあるのかは本論文からは分からない。三モジュール拡張の実験で Gurobi が下界の供給源として登場していることが、その差を間接的に示している。

三モジュール拡張の評価設計は控えめに読むべきだと考える。 テストインスタンスが7件で、Solved Ratio の 57% → 71% は「4件から5件へ」の差である。著者ら自身が「概念実証」と書いているとおり、統計的な主張としては弱い（この読みは自分の評価）。

読後に残った問い

• 二時間尺度の比 ω_c : ω_b = 4 : 1 はどう決まったのか。感度分析は本文にない。
• 学習コストが報告されていない。時間指標はモデルの学習時間を含まないと明記されているが、問題クラスごとに別モデルを学習する構成では、実務での採算は学習コスト次第になる。
• カットを根ノードに限定しない設計を先行研究との差として挙げているが、木の深い位置でのカット追加が汎化にどう効いているかは分解されていない。

付録

関連して読むもの

• 同じ「求解を速くする」目的を、ソルバー内部ではなく定式化そのものの書き換えから狙う研究として FormuEvo がある。Collab-Solver が過程（切除平面と分岐）を、FormuEvo が入口（モデルの書き方）を扱う。
• 本論文は問題クラスごとに別モデルを学習し、クロスクラス汎化を今後の課題としている。その「どのインスタンスを同じクラスとみなすか」を定式化から直接定める試みが MILPインスタンス間の距離尺度 である。

参照箇所