Upgrade to Pro — share decks privately, control downloads, hide ads and more …

論文読み会 AAAI2022 | MIP-GNN: A Data-Driven Framewo...

cocomoff
January 04, 2023

論文読み会 AAAI2022 | MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers

論文読み会の資料です.

(A slide for the paper-reading activity at my company, written in Japanese.)

cocomoff

January 04, 2023
Tweet

More Decks by cocomoff

Other Decks in Research

Transcript

  1. MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers 著者: Elias

    B. Khalil, Christopher Morris, Andrea Lodi (Univ. of Toronto, McGill University, Cornell Tech) 学会: AAAI2022 @cocomoff 1/20
  2. 概要 やりたいこと 組合せ最適化ソルバーをデータ駆動型でサポートする 分枝限定法で どのノードを次に選択するか (node selection) どの変数を分枝するか (branching variable

    selection) やったことの概要 0-1整数計画問題(Binary Linear Programming; BLP) を考える 表現力の高い問題クラス 具体的にはGISP (Generalized Independent Set Prolbem) / FCMNF (Fixed-Charge Multi-Commodity Flow problem) で実験 ソルバーを使ってそこそこの解を計算し、学習に使う 最適化問題の変数バイアス(Variable bias、後で説明)をGNNで推定 変数バイアスの予測値を使ってスコアリング手法を提案 ついでに解のwarm-startとかもできる 2/20
  3. 補足: 分枝限定法 Qiita: 「図で見る分枝限定法」より図を引用 ナップサック問題(あるアイテムについて、0 (入れない)・1 (入れる) を決める) node selection:

    次にどの部分木を調べるか決める branching variable selection: まだ展開して決定していない二値変数のう ち、どれを次に展開するかを決める 5/20
  4. 補足: 変数バイアス CNF-SAT に対して定義された概念 [1] 例題: 3つの節、 変数の式 SATインスタンス 変数割当

    が を充足する が真 補足: 変数バイアス(Bias) 充足可能な について、変数 の(推定された)バイアス分布 とは、 の充足可 能な割当について変数 が真 (または偽) で現れる割合を表す positive/negative bias ( ) 全ての変数についてのバイアスをベクトルに格納したものを Survey/Profile と呼ぶ 余談: 名前が一般的過ぎてググっても情報が出てこない… 要するに「どれぐらい真 (または偽)を取り得るか」の情報 [1] E.I. Hsu et al., Probabilistically Estimating Backbones and Variable Bias: Experimental Overview, Proceedings of CP2008, pp.613-617, 2008 / 同著者のAAAI2008 Workshopの論文もある。 6/20
  5. 補足: LP、BLP (0-1 ILP) 線形計画問題 (LP) は 3つ組 で定義される ぐらいの範囲を考える

    feasible set LPの目的: Simplex法や内点法で解ける 整数線形計画問題 (ILP) は 3つ組 で定義される ただし feasible set に制限する場合、BLP (0-1 ILP) と呼ぶ あるBLPのインスタンス から整数性を落とした問題 を緩和問題と呼ぶ 分枝限定法 分枝操作と限定操作を用いた一般解法で全てのソルバーで使われている 分枝操作: 変数の場合分け 限定操作: 見積もった最適値による枝刈り 内部で切除平面法と合わせた場合に分枝切除法と呼ばれることも 7/20
  6. 学習問題の設定 | BLPの場合の変数バイアス 実世界の何らかの分布から作られたインスタンスの集合 を考える あるインスタンス について、near-optimal solutions の集合 (tolerance

    ) を定義する 変数バイアスベクトル を以下で定義する -near optimal solutionの中で、各決定変数が だった割合のベクトル CNF-SATの変数バイアスのベクトル (Survey/Profile) と同じ 凄い強そうな情報だが、計算がヤバそう これを教師あり学習で近似する (MIP-GNN) のが提案アプローチ 9/20
  7. 学習問題の設定 | 教師あり学習 普通の教師あり学習を考える。記号: : インスタンス集合 の上の分布 : 有限の学習集合インスタンスの集合 (分布

    でサンプル) 予測モデル はインスタンス の決定変数の集合 パラメータ ロス関数 教師あり学習 直感的には が面倒そうだけど、GNNに任せたらいけそう ポイント: 変数と制約に注目して、二部グラフを作った上でGNNを動かす 10/20
  8. MIP-GNN: アーキテクチャ 二部グラフ (制約cと変数vのパート) v cの伝搬(左)、c v の伝搬(右) これを交互に繰り返す (iterate)

    特徴ベクトル ( 層目): 目的関数の (紛らわしい) の情報もここに入れる v → c はベクトルの連結、普通のGNN c → v 各変数 に対して を求め、ベクトル を得る 制約 の違反量をsoftmaxで測定する: 誤差ベクトルは次段のvariable embedding更新に使う 13/20
  9. MIP-GNN: 学習と評価 学習 -near optimal solutionを既存のソルバーで探して学習する 正確な値 を予測しなくても、 に近いかどうか?が知れたら十分に嬉しい しきい値

    で加工した二値分類問題として学習させる もし であれば を、そうでなければ を当てる MIP-GNNで最後にMLPを通して推定したスコアは、以降の活用フェーズ(右側)では で表す 評価 | 確信スコア MLPを通して出力されたベクトル に対して、変数 の確信度を定義: は の近い方に丸める操作 どれぐらい予測が整数に近いかを表す 14/20
  10. MIP-GNN: 解のwarm-start スコアを見て、直接近似解を求められそう: しきい値 を用いて 適当に丸めているだけなのでfeasibleではない解になる、CPLEXには壊れた解を feasibleに直す機能(repair)があるので、それに突っ込めばOK よく知りません… (これはただのメモ) node-selection、branching

    variable selection、warm-startの3要素 branching variable selectionはサポートしてない(説明なし?)? ついでに、ソルバーを使って -near optimal solutionの準備は必要なので、 それはそれで大変な気がする(60分と書いてあった、詳細は知らない) 16/20