論文の概要: Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization

• arxiv url: http://arxiv.org/abs/2608.30103v1
• Date: Mon, 31 Aug 2026 00:32:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-01 18:31:31.179436
• Title: Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization
• Title（参考訳）: Graph4BiLO:二値混合整数線形最適化のためのグラフニューラルネットワーク近似
• Abstract要約: 本稿では,変数制約グラフ表現から2レベル値関数を学習するためのグラフニューラルネットワーク(GNN)アプローチであるGraph4BiLOを紹介する。 固定長多層パーセプトロン(MLP)表現とは対照的に、GNNは共有メッセージパッシングパラメータを使用する。 我々は,MibSソルバと学習ベースNeur2BiLO法に対して,20-100項目のknapsackインターディクションインスタンス上でGraph4BiLOを評価する。
• 参考スコア（独自算出の注目度）: 5.747894139981667
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel mixed-integer linear optimization problems model hierarchical decision processes in which a leader anticipates the optimal response of a follower. Although expressive, these problems are computationally challenging because lower-level optimality is embedded in the leader's feasible region. Value-function reformulations replace the nested follower optimization with a constraint involving the follower's optimal value, but evaluating this value function exactly can itself be expensive. This paper introduces Graph4BiLO, a graph neural network (GNN) approach for learning bilevel value functions from variable--constraint graph representations. In contrast to fixed-length multilayer perceptron (MLP) representations, the GNN uses shared message-passing parameters and can therefore be applied across multiple problem sizes with a single trained model. The learned ReLU network is encoded exactly as mixed-integer linear constraints and embedded in an approximate single-level formulation. A repair step subsequently re-solves the follower problem for the selected leader decision to recover a bilevel-feasible follower response. We evaluate Graph4BiLO on knapsack interdiction instances with 20--100 items against the exact MibS solver and the learning-based Neur2BiLO method. Graph4BiLO obtains objective values comparable to Neur2BiLO across all tested sizes while avoiding size-specific neural networks. An additional out-of-distribution experiment demonstrates zero-shot transfer from 20-item training instances to previously unseen 40- and 60-item instances. However, embedding message passing at every graph node substantially increases the resulting mixed-integer formulation size and solve time. These results identify a central tradeoff between size-generalizable graph representations and the computational cost of embedding GNNs within optimization models.
• Abstract（参考訳）: 双方向混合整数線形最適化問題は、リーダーがフォロワーの最適応答を予測する階層的決定過程をモデル化する。 表現的ではあるが、これらの問題は、低いレベルの最適性がリーダーの実現可能な領域に埋め込まれているため、計算的に困難である。 値関数の修正は、ネストされた追従者の最適化を、従者の最適値を含む制約に置き換えるが、この値関数を正確に評価することは、それ自体が高価である。 本稿では,変数制約グラフ表現から2レベル値関数を学習するためのグラフニューラルネットワーク(GNN)アプローチであるGraph4BiLOを紹介する。 固定長多層パーセプトロン(MLP)表現とは対照的に、GNNは共有メッセージパッシングパラメータを使用し、1つの訓練されたモデルで複数の問題サイズに適用できる。 学習されたReLUネットワークは、正確に混合整数線形制約として符号化され、近似した単一レベル定式化に埋め込まれる。 その後、修理工程は、選択されたリーダ決定に対するフォロワー問題を再解決し、バイレベル可能なフォロワー応答を回復する。 我々は,MibSソルバと学習ベースNeur2BiLO法に対して,20-100項目のknapsackインターディクションインスタンス上でGraph4BiLOを評価する。 Graph4BiLOは、サイズ固有のニューラルネットワークを避けながら、すべてのテストサイズでNeur2BiLOに匹敵する客観的値を取得する。 新たなアウト・オブ・ディストリビューション(out-of-distriion)実験では、20-itemのトレーニングインスタンスから、これまで見つからなかった40-itemインスタンスと60-itemインスタンスへのゼロショット転送が示されている。 しかし、各グラフノードにメッセージパッシングを埋め込むと、結果の混合整数の定式化サイズが大幅に増加し、時間も短縮される。 これらの結果から,最大化可能なグラフ表現と最適化モデルにGNNを埋め込む計算コストとの間の中心的なトレードオフが明らかになった。

関連論文リスト

• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• BloomGML: Graph Machine Learning through the Lens of Bilevel Optimization [20.356581011483215]
  本稿では,二段階最適化の特別事例として,様々なグラフ学習手法を再キャストする方法を示す。 まず、より柔軟なエネルギー関数のクラスを導出し、様々な降下ステップと組み合わせると、グラフニューラルネットワーク(GNN)メッセージパッシング層を形成する。 次に,このフレームワークを単純化して,非GNNグラフ学習手法との密接な関係を導出する。
  論文  参考訳（メタデータ） (2024-03-07T18:57:46Z)
• Neur2BiLO: Neural Bilevel Optimization [15.876446950057389]
  双方向最適化は、リーダーが目的の機能を最小化する最初の決定を下すネストした問題を扱う。 Neur2BiLOは、リーダーまたはフォロワーの値関数のニューラルネットワーク近似を、教師付き回帰を通じてトレーニングし、簡単に解ける混合整数プログラムに組み込む。
  論文  参考訳（メタデータ） (2024-02-04T15:54:37Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  グラフニューラルネットワーク(GNN)は、グラフタスクに対して有望な結果を示す。 既存のGNNの一般化能力は、テストとトレーニンググラフデータの間に分散シフトが存在する場合に低下する。 本稿では,分布外一般化能力を大幅に向上させる非線形グラフデコリレーション法を提案する。
  論文  参考訳（メタデータ） (2023-12-19T12:25:10Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• $\rm A^2Q$: Aggregation-Aware Quantization for Graph Neural Networks [18.772128348519566]
  グラフニューラルネットワーク(GNN)のための集約型混合精度量子化(rm A2Q$)を提案する。 本手法は,ノードレベルのタスクとグラフレベルのタスクで最大11.4%,9.5%の精度向上を実現し,専用ハードウェアアクセラレータで最大2倍の高速化を実現する。
  論文  参考訳（メタデータ） (2023-02-01T02:54:35Z)
• DOGE-Train: Discrete Optimization on GPU with End-to-end Training [28.795080637690095]
  0-1整数線形プログラムの緩和を解くために,高速でスケーラブルなデータ駆動型手法を提案する。 グラフニューラルネットワーク(GNN)とラグランジュ分解に基づくアルゴリズムであるFastDOGを用いる。
  論文  参考訳（メタデータ） (2022-05-23T21:09:41Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Graph-adaptive Rectified Linear Unit for Graph Neural Networks [64.92221119723048]
  グラフニューラルネットワーク(GNN)は、従来の畳み込みを非ユークリッドデータでの学習に拡張することで、目覚ましい成功を収めた。 本稿では,周辺情報を利用した新しいパラメトリックアクティベーション機能であるグラフ適応整流線形ユニット(GRELU)を提案する。 我々は,GNNのバックボーンと様々な下流タスクによって,プラグアンドプレイGRELU法が効率的かつ効果的であることを示す包括的実験を行った。
  論文  参考訳（メタデータ） (2022-02-13T10:54:59Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。