「A Distance Metric for Mixed Integer Programming Instances」を読む

要旨

MILP は幅広い実問題を表現できる一方、インスタンス同士を比較する構造を持たない。信頼できる類似度があれば、ベンチマーク集合の異質性を定量化でき、機械学習をソルバーに組み込む研究（ML-MILP）にも指針を与えられる。既存の類似度はクラス識別の精度が低いか、ラベル付きデータへの依存が強く、適用範囲と汎化が限られる。

著者らは、MILPインスタンス間の数学的距離を、定式化から直接導く形で初めて定義した。右辺・変数・重みをそれぞれ少数のクラスに離散化し、制約内の重み・変数ペアの出現割合と、インスタンス内の制約の出現割合という正規化表現を作る。これによりインスタンスの大きさに由来する次元が落ち、規模の異なるインスタンスを比較できる。

距離は二段の最適輸送として定義される。制約間の距離は重み・変数ペアの割合を最小コストで輸送する Earth Mover’s Distance（EMD）に右辺の不一致項を足したもの、インスタンス間の距離は制約の割合を最小コストで輸送するEMDに目的関数の距離項を足したものである。EMD に帰着することで、距離の公理を満たすことが示される。

StrIPLIB を使い、19クラスの識別と3クラス内のサブクラス識別で評価した。各成分（重み α、変数 β、右辺 γ、目的関数 ζ）を一つずつ落とす感度分析では、いずれもクラス識別に寄与していた。貪欲版は19クラス中17クラスで厳密版と同一の結果を出しながら、約200倍高速だった。特徴量ベースと画像ベースの非学習手法は明確に上回り、教師ありGNNとは同等圏に並ぶ。

用語・記号

課題・結果・結論の対応

flowchart LR
    P1["P1<br/>MILP空間に<br/>構造がない"] --> M["正規化表現 +<br/>二段のEMD"]
    P2["P2<br/>既存尺度は精度不足か<br/>ラベル依存"] --> M
    P3["P3<br/>EMDの厳密計算は<br/>O(n³log n)"] --> M2["貪欲ヒューリスティック"]
    M --> R1["R1<br/>全成分が<br/>クラス識別に寄与"]
    M --> R2["R2<br/>非学習手法を凌駕し<br/>教師ありGNNと同等"]
    M2 --> R3["R3<br/>17/19クラスで同一結果<br/>約200倍高速"]
    R1 --> C1["C1<br/>学習なしで<br/>構造を捉えられる"]
    R2 --> C1
    R3 --> C2["C2<br/>実用的な計算量で<br/>組み込める"]

図：数学的距離としての正当性（M）と実用的な計算量（M2）を分けて示し、それぞれ別の実験で裏づける構成になっている。

背景

MILP は目的関数を線形制約のもとで最適化し、連続変数と離散変数の両方を含む。輸送、製造、e-ヘルスなど幅広い分野の実問題を表現できる。

一方、インスタンス同士の関係という点では MILP 空間は広大で構造を欠いている。ここに構造を入れる利点として、著者らは二つを挙げる。第一に、インスタンス集合の性格づけができる。MIPLIB 2017 のように異質性の高いベンチマークを作ったり、評価集合の異質性を測って手法の汎化性を判断したりできる。第二に、構造情報はソルバーの性能を押し上げうる。とくに ML-MILP は、似たインスタンスの限られた部分集合の中でしか有効性を示せていない。MILP 空間を同質なインスタンスの塊に分割することは、ML-MILP を広い領域へ広げる前提になる。

MILP 空間を構造化する初期の試みは、実世界の問題型に基づく問題クラスの定義だった。これは MILP 空間の一部しか覆えない。全体を覆うためにタグ付けが導入されたが、タグは階層的で一つのインスタンスが複数のタグを持つため、互いに交わらないクラスへの分割にはならない。

類似度側では三つの手法がある。ISS は制約行列を濃淡画像として自己符号化器に通すが、制約の並び順に敏感である。GNN ベースの手法は順序不変なグラフ表現でこれを解決したが、事前学習した問題クラスにしか使えない。MIPLIB 2017 の枠組みは100を超える手作り特徴量で高次元空間に埋め込むが、特徴選択と正規化に理論的裏づけがなく頑健性を欠く。

課題

P1：MILP 空間に、インスタンスを結ぶ構造がない

ML-MILP の手法は合成データセットか特定の問題クラスに限られたベンチマークで学習されることが多く、汎化はインスタンスの規模を変えて評価されるのが普通で、構造的な多様性では評価されない。結果として、異質な実世界インスタンスへの汎化に失敗しがちである。また多くの研究が独自の評価集合を定義し、その異質性を原理的に評価していないため、汎化能力の観点での手法比較が難しい。

P2：既存の類似度は、精度不足かラベル依存かのどちらかである

非学習の特徴量ベース手法は、特徴選択に厳密な正当化がなく、多様なMILP定式化への適用に確信が持てない。ISS は GNN ベースに劣ることが示されている。一方の教師ありGNNは学習時に事前定義のクラスを必要とし、MILP 空間全体に対する原理的な構造を定めるという枠組みとしては一貫性を欠く。MILP 全体の多様性へ汎化させようとすると、適切な学習集合の選定が難しくなる。

P3：EMD の厳密計算は高コストである

EMD の厳密計算は O(n³log n) であり、本論文では制約レベルとインスタンスレベルの二段で使うため、計算コストが実用上の障害になる。

問題設定

MILP インスタンス P を次の形で置く。

Minimize  z = Σ_{j ∈ N_0} w_0^j v^j
s.t.      i ∈ {1, …, m},  c_i : Σ_{j ∈ N_i} w_i^j v^j ≤ b_i

• (v^j)：インスタンスの変数の集合
• C = (c_i)：制約の集合。c_0 は慣例として目的関数を指す
• b_i：制約 c_i の右辺
• (w_i^j)：制約 c_i における変数の重み

狙いは、同じ問題クラスに属するインスタンスを、大きさが違っても似ていると判定する距離を定めることである。具体的には次の二つに距離 0 を与えたい。

1. 変数の個数は違うが、重み・変数ペアの分布の比率が保たれている制約どうし
2. 制約の個数は違うが、似た制約が同じ割合で現れているインスタンスどうし

なお著者らは、MILP 空間を実際に分割する作業は本論文の範囲外だと明記している。ここでの目的は距離そのものの妥当性と頑健性の検証である。

手法

中心的な着想は、インスタンスから規模に由来する次元を落として「割合の分布」にしてしまえば、構造の比較は最適輸送で書けるということである。

特徴のクラス化

距離を定義するために、MILP の三つの基本要素を離散クラスへ落とす。

• 変数：標準的な三分類、二値 B、整数 I、連続 C。上下限の制約はクラス数を抑えるため除く
• 重みと右辺：区間で切ると境界の扱いが問題になるため、最も頻出する特異点を個別のクラスとして切り出し、残りを補集合クラスにまとめる

クラスの決め方は MIPLIB 2017 の1065インスタンスから導いている。重みでは -1（40%）と 1（33%）、右辺では 0（57%）と 1（21%）が最頻の特異点で、この出現率の高さが特異点ベースの妥当性を裏づける。StrIPLIB でも同様の傾向が見られる。結果として次のクラス分けになる。

三種とも同じクラス数にし、クラス比率を均すことで、特徴ごとの重要度を比較しやすくし、どれか一種が類似度計算を支配しないようにしている。離散化の方針はエントロピーに基づく離散化の考え方を参照している。

正規化表現

このクラス化により、制約内では重み・変数ペアの重複が、制約間では構造的に同一な制約の重複が見えるようになる。

• p_c(ŵ, v̂, i)：制約 c_i の中でペア (ŵ, v̂) が占める割合
• p_P(P, c_i)：インスタンス P の中で構造的に同一な制約 c_i が占める割合

インスタンスをこの二種の割合で書き直したものが正規化表現である。論文が挙げる例では、MIPLIB 2017 の app1-2 は53467制約・26871変数を持つが、構造的に異なる制約表現は13種しかなく、各表現に含まれる重み・変数ペアの型はたかだか3種である。

著者らは、この標準化が MIPLIB 2017 の手作業による制約テンプレートと強く似ていること、そしてテンプレートの定義を自動化・一般化するものであることを指摘している。

二段の最適輸送としての距離

重み・変数ペアの距離。 重みのクラスが違えば α > 0、変数のクラスが違えば β > 0 を足す。

d_wv(ŵ_j, v̂_k, ŵ_l, v̂_o) = α·1(ŵ_j ≠ ŵ_l) + β·1(v̂_k ≠ v̂_o)

これは離散距離であり、距離の公理を満たす（定理1）。

制約間の距離。 制約 c_q から c_r へ、重み・変数ペアの割合を移す最小コストとして定義する。コストは d_wv で重みづけられ、右辺のクラスが違う場合の項 γ·1(t(b_q) ≠ t(b_r)) を足す。輸送量 f は非負で、各ペアからの総輸送量が c_q 側の割合に、各ペアへの総輸送量が c_r 側の割合に等しいという制約を持つ。第一項がまさに EMD（Wasserstein 距離）にあたる。距離に距離を足した形なので、全体も距離になる（定理2）。

インスタンス間の距離。 同じ構図を一段上げる。P_s の制約の割合を P_t の制約へ移す最小コストを d_c で重みづけ、目的関数の距離 ζ·d_c(c_0(P_s), c_0(P_t)) を足す（定理3）。

結果として、構造的に同一の制約が同じ割合で現れるインスタンス同士は距離 0 になり、一般の場合は「正規化表現の上で一方を他方に変えるのに必要な変更の最小割合」を測ることになる。重みの変更は α、変数の変更は β、右辺の変更は γ のペナルティを受け、目的関数の差には ζ が掛かる。

著者ら自身が挙げる既知の限界として、この定式化は次元に対して柔軟すぎる。変数が1個だけ現れる制約と、その変数が複数回現れる制約との距離が 0 になりうるが、意味は大きく違いうる。

貪欲ヒューリスティック

厳密な EMD の代わりに、最も近いペアから順に割り当てる貪欲法を使う。制約レベルでは、一方の制約の重み・変数ペアを d_wv に基づいて最も近い相手と順に対応づけ、対応量は両者の割合の小さいほうとする。一つの制約に現れる異なるペアはたかだか |C(w)| × |C(v)| 種なので、制約2本の比較は O(|C(w)|²×|C(v)|²) である。インスタンス全体では制約の異なり数 |M(P_s)|、|M(P_t)| を掛けた O(|C(w)|²×|C(v)|²×|M(P_s)|×|M(P_t)|) になる。インスタンスレベルの対応づけは O(|M(P_s)|×|M(P_t)|) で、制約レベルに比べて無視できる。

課題との対応

詳細

データ・評価手順

StrIPLIB を使う。21000件超の MILP インスタンスを階層的なクラス・サブクラスに整理したデータセットである。MIPLIB 2017 は実世界インスタンスが複数の問題型にまたがることが多く、クラスベースの評価に向かないため意図的に避けている（ただし重みと右辺のクラス分けは MIPLIB の観察から導かれている）。

評価は次の手順による。

1. 各クラス（またはサブクラス）から50件を抽出し、テスト10件・参照40件に分ける
2. 各テストインスタンスについて、全クラスの参照インスタンスとの距離を計算する
3. 距離の小さい順に参照40件を選ぶ
4. そのうち正しいクラスに属する割合を top-40 accuracy とする
5. クラスごとのスコアは、その10件のテストインスタンスの平均とする

クラスを増やすとテストインスタンスあたり40点の比較対象が増えるため、性能はクラス総数に依存する。したがって結果は同一実験内でのみ比較でき、実験をまたいだ比較はできない。

比較手法

著者らが把握する限り、MILPインスタンス間の類似度として確立しているのは次の三つだけである。

• Feat：MIPLIB 2017 の100次元手作り特徴量。特徴空間でのユークリッド距離。公開されている特徴抽出コードを使用。他のベースラインとの直接比較は先行研究では行われていない
• ISS：制約行列を濃淡画像にして自己符号化器に通し、出力ベクトルのユークリッド距離を取る。実装が公開されていないため、第1実験では原論文の報告値を用い、第2実験からは除外
• GNN：19クラスへ分類するよう学習した GNN の埋め込み間のユークリッド距離。学習コードは公開されていないため、同一枠組みの実験は報告値を、追加実験は公開済み学習済みモデルを使用

結果

R1（P1 に対応）：各成分がクラス識別に寄与する

第1実験は StrIPLIB の19問題クラスを対象に、先行研究と同じ枠組みで行われた。提案手法（Formal）のうち一つの重みを 0 にした版（α、β、γ、ζ を打ち消した版）と、全パラメータを 1 にした完全版（∅）、および厳密版（∅E）を比べている。感度分析の各版はすべて貪欲版である。

いずれかの成分を落とすと概ね性能が下がる。完全版は α を落とした版と ζ を落とした版を一貫して上回り（後者は1クラスを除く全クラスで）、β を落とした版に対しても3クラスを除いて上回る。右辺の比較を落とした版（γ）は平均では完全版と同程度だが、最悪ケースの落ち込みが大きく（最大19%）、ばらつきと不安定さが大きい。

クラス別に見ると、10を超えるクラスで top-40 accuracy が 95% を超える一方、明確に劣るクラスもある。著者らの追加分析では、クラス間の構造的な重なりが原因として挙がる。Formal が返す上位40件の少なくとも10%が別クラスに属する場合があり、逆も起きる。bpp と cut は StrIPLIB の文書でも構造的に似ていると明記されており、cpm と cwl はどちらも容量制約つきの定式化、map と col は別クラスながら似た構造を持つ。rel はどの尺度でも成績が悪く、内部の異質性の高さと bif との重なりが原因と見られる。これらの重なりは、インスタンスクラスの定義そのものが本質的に曖昧であることから生じているとされる。

R2（P2 に対応）：非学習手法を凌駕し、教師ありGNNと同等圏に並ぶ

19クラス識別の平均 top-40 accuracy は次のとおりである。

Formal と GNN はいずれも Feat と ISS を一貫して上回る。後者2つは19クラス中12クラスで最良スコアより50%以上悪い。GNN は同種クラスの約800件のラベル付きインスタンスで教師あり学習しているにもかかわらず、両者の差は小さい。最良スコアの5%以内に収まったのは Formal が19クラス中12、GNN が14である。

第2実験はサブクラス識別で、より近いインスタンス同士を区別する分だけ本質的に難しい。GNN の学習枠組みに合わせるため、対象は GNN が学習したクラスの中から、(i) GNN の参照集合に含まれる、(ii) サブクラスが50件以上を含む、(iii) 1クラスにつき複数のサブクラスが該当する、の条件で選び、3クラス・各3〜4サブクラスになった。

クラスごとに見ると挙動が違う。bpp では GNN が2つのサブクラスで Formal を 48% と 16% 上回るが、bpp の4サブクラスのうち3つは GNN が個別のクラスとして学習済みであり、有利な条件にある。lot では各手法が2サブクラスずつで優位に立つが、GNN は最良から52%以上落ちるケースがあるのに対し、Formal は最良から6%以上落ちることがなく、信頼性で勝る。vrp では GNN が完全分類を達成し、Formal は平均で約10%の差で続く。

R3（P3 に対応）：貪欲版は厳密版とほぼ同一の精度で約200倍速い

貪欲版（∅）と厳密版（∅E）を比べると、19クラス中17クラスで結果が一致する。テストインスタンスあたりの上位40近傍を求める平均計算時間は、貪欲版が 2.8×10⁻³ 秒（標準偏差 4.4×10⁻³）、厳密版が 0.37 秒（標準偏差 0.65）である。論文はこれを約200倍の高速化と述べ、あわせて計算時間のばらつきも大幅に小さいことを指摘し、実用上は貪欲版が明らかに望ましいと結論している。

結論

C1（P1・P2・R1・R2 に対応）

MILP に対して、距離の公理を満たす新しい類似度を導入した。この尺度は比較対象の問題が持つ内在的なデータだけから導かれ、学習過程を一切必要としない。検討したベースラインを上回り、とくにラベル付き学習データに依存する分類手法に対抗できることを示した。

利点として二つが挙げられている。第一に、インスタンス集合の異質性を性格づけられるため、異質なベンチマークの選定や評価集合の多様性の定量化に使える。第二に、インスタンスの目的そのものを見なくても、制約の構造表現だけでクラスを定義できる。これにより既存のクラスを橋渡しし、ラベルのない、あるいはラベルの乏しいインスタンスを既知の集団へ結びつけられる。

C2（P3・R3 に対応）

貪欲版は厳密版とほぼ同一の精度を保ちながら計算時間を2桁縮め、ばらつきも小さい。実用への組み込みを考えるなら貪欲版を選ぶべきである。

考察

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

本文中で明示されている限界は、次元に対する柔軟さである。変数が1個現れる制約と、その変数が複数回現れる制約の距離が 0 になりうるが、意味は大きく異なる。

今後の課題は、この方法論を MILP 空間全体の分類へ拡張することである。ML-MILP はおおむね構造的に似たインスタンスでしか良い性能を出さないため、MILP 空間の網羅的な分類ができれば、クラスごとに特化した ML-MILP モデルを作れるようになる。

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

「凌駕した」相手を取り違えないほうがよい。 Formal が明確に上回るのは非学習のベースライン（Feat 38、ISS 40）であって、教師ありGNNではない。クラス識別の平均では GNN 83 に対して Formal 73 で、GNN のほうが高い。Formal が並ぶのはサブクラス識別（77 対 76）である。論文自身も「どちらが優れているかを決定的に判断するのは難しい」と書いており、主張は「ラベル760件で学習した分類器と同等圏に、教師なしで到達した」である。この違いは手法を選ぶときに効く。

本当の売りは精度より制約条件のほうだと思う。 GNN は事前定義された19クラスで学習されているため、その枠の外へは出られない。Formal は学習が要らず、任意のインスタンス対に定義でき、しかも距離の公理を満たす。距離の公理を満たすということは、近傍の定義やクラスタリングなど距離を前提とするアルゴリズムをそのまま載せられるということで、「MILP空間を分割する」という最終目標への道具立てとしてはこちらのほうが効く。GNN の埋め込み間のユークリッド距離も形式的には距離だが、埋め込み自体が学習クラスに縛られている。

「約200倍」は報告された実測値と少しずれる。 論文の数字をそのまま割ると 0.37 / 2.8×10⁻³ ≒ 132 倍である。200倍という表現は別の測り方に基づく可能性があるが、本文からは特定できない。いずれにせよ2桁の高速化という結論は変わらない（この算術は自分で確認したもの）。

評価の枠組みが先行研究の設定に縛られている。 19クラスという選択は先行研究から引き継いだもので、その50件の選び方は原論文に記載がないと著者ら自身が書いている。加えて、ライブラリの更新で50件超を持つクラスが6つ増え、bpp・bp2・bif は現在サブクラスに再分類されている。つまり評価に使ったクラス分けは、最新の StrIPLIB の分類とすでに食い違っている。比較可能性を優先した判断だと思うが、絶対的な精度の数字としては割り引いて読むべきである。

クラス間の重なりは尺度の欠陥ではなく、正解ラベル側の問題である。 bpp と cut の混同は StrIPLIB の文書自身が両者の構造的な近さを認めている。この論文の尺度が「連続的な構造的近さ」を測る以上、離散クラスを正解とする評価では上限がある。むしろ距離が示す重なりのほうが、既存のクラス分けの粗さを可視化していると読める。

読後に残った問い

• α = β = γ = ζ = 1 は感度分析での基準設定であり、最適化された値ではない。用途（ベンチマーク構成か、ML-MILP の学習集合選定か）によって重みを変えるべきではないのか。
• 距離が 0 になる条件は「構造的に同一の制約が同じ割合で現れる」ことだが、この割合ベースの正規化は、大きいインスタンスに少数だけ現れる特殊な制約を無視してしまう。その少数の制約が求解の難しさを決めている場合、距離は近いのに解きやすさは全く違う、という事態が起きないか。
• 最終目標である MILP 空間の分割は範囲外とされている。この距離でクラスタリングしたときに、既存のクラス分けとどれだけ一致し、どこがずれるのかは次の論文を待つことになる。

付録

関連して読むもの

• この距離の動機になっている「ML-MILP は同質なインスタンス集合でしか効かない」状況の具体例として Collab-Solver がある。あちらは問題クラスごとに別モデルを学習し、クロスクラスの汎化を今後の課題に挙げている。
• 一方、定式化そのものを問題族単位で作り替えて速くする FormuEvo は、蒸留知識を問題間で転移させる。「どの問題族が構造的に近いのか」を定量化する手立てとして、この距離は同じ問いに別の側から触れている（両論文の間に直接の引用関係はない）。

参照箇所