論文の概要: On Representing Mixed-Integer Linear Programs by Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2210.10759v2
• Date: Thu, 25 May 2023 20:01:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-29 23:38:13.646837
• Title: On Representing Mixed-Integer Linear Programs by Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークによる混合整数線形プログラムの表現について
• Authors: Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, Wotao Yin
• Abstract要約: 混合整数線形プログラミング(MILP)は一般にNPハードであるが, 実用的MILPは過去20年間で約100倍の高速化を実現している。 しかし、全てのGNNが平等に扱うような、実現不可能で実現不可能なMILPが存在する。 我々は、MILPを展開可能なものに制限したり、ランダムな特徴を加えることで、MILPの実現可能性、最適目標値、最適解を所定の精度で確実に予測できるGNNが存在することを示す。
• 参考スコア（独自算出の注目度）: 30.998508318941017
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While Mixed-integer linear programming (MILP) is NP-hard in general, practical MILP has received roughly 100--fold speedup in the past twenty years. Still, many classes of MILPs quickly become unsolvable as their sizes increase, motivating researchers to seek new acceleration techniques for MILPs. With deep learning, they have obtained strong empirical results, and many results were obtained by applying graph neural networks (GNNs) to making decisions in various stages of MILP solution processes. This work discovers a fundamental limitation: there exist feasible and infeasible MILPs that all GNNs will, however, treat equally, indicating GNN's lacking power to express general MILPs. Then, we show that, by restricting the MILPs to unfoldable ones or by adding random features, there exist GNNs that can reliably predict MILP feasibility, optimal objective values, and optimal solutions up to prescribed precision. We conducted small-scale numerical experiments to validate our theoretical findings.
• Abstract（参考訳）: Mixed-integer linear programming (MILP) は一般にNP-hardであるのに対し、実践的なMILPは過去20年間で約100倍のスピードアップを受けている。 それでも多くのミルプのクラスは、そのサイズが大きくなるとすぐに解決不能になり、研究者がミルプの新しい加速技術を探す動機となった。 深層学習では実験結果が強く,MILPソリューションプロセスの様々な段階における決定にグラフニューラルネットワーク(GNN)を適用することにより,多くの結果が得られた。 しかしながら、全てのGNNが同等に扱い、一般的なMILPを表現する能力が欠如していることを示す、実現不可能なMILPが存在する。 次に,ミルプを展開可能なものに制限したり,ランダムな特徴を加えたりすることで,ミルプ実現可能性,最適目的値,最適解を所定の精度で確実に予測できるgnnが存在することを示す。 理論的結果を検証するため, 小規模数値実験を行った。

関連論文リスト

• Heuristic Learning with Graph Neural Networks: A Unified Framework for Link Prediction [25.87108956561691]
  リンク予測はグラフ学習における基本的なタスクであり、本質的にグラフのトポロジーによって形作られる。 種々の重みを適応・一般化するための統一行列定式化を提案する。 また,この定式化を効率的に実装するためのHuristic Learning Graph Neural Network (HL-GNN)を提案する。
  論文  参考訳（メタデータ） (2024-06-12T08:05:45Z)
• Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs [40.99368410911088]
  二次計画法 (QP) は非線形計画法において最も広く適用されている分野である。 QPタスクにグラフニューラルネットワーク(GNN)を適用する最近の研究は、GNNが最適化インスタンスの重要な特徴を捉えることができることを示している。 本稿では,2次プログラムの重要な特性を確実に表現できるメッセージパスGNNの存在を実証する。
  論文  参考訳（メタデータ） (2024-06-09T23:57:47Z)
• AdaGMLP: AdaBoosting GNN-to-MLP Knowledge Distillation [15.505402580010104]
  GNN-to-MLPナレッジ蒸留と呼ばれる新しい手法の波が出現した。 彼らは、より効率的な学生にGNN学習の知識を移すことを目標としている。 これらの手法は、不十分なトレーニングデータと不完全なテストデータを持つ状況において課題に直面している。 本稿では,AdaBoosting GNN-to-MLPナレッジ蒸留フレームワークであるAdaGMLPを提案する。
  論文  参考訳（メタデータ） (2024-05-23T08:28:44Z)
• Rethinking the Capacity of Graph Neural Networks for Branching Strategy [40.99368410911088]
  グラフニューラルネットワーク(GNN)は、混合整数線形プログラム(MILP)の特性を予測するために広く利用されている。 本稿では,強い分岐(SB)を示すGNNの能力について検討する。 我々はMP-GNNがSBスコアを正確に近似できる「MP-tractable」MILPのクラスを定義する。
  論文  参考訳（メタデータ） (2024-02-11T04:09:50Z)
• MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
  特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。 このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。 本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
  論文  参考訳（メタデータ） (2023-10-29T20:32:21Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  本稿では、P(ropagational)MLPと呼ばれる中間モデルクラスを導入することにより、GNNの性能向上を本質的な能力に向ける。 PMLPは、トレーニングにおいてはるかに効率的でありながら、GNNと同等(あるいはそれ以上)に動作することを観察する。
  論文  参考訳（メタデータ） (2022-12-18T08:17:32Z)
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks [80.55378250013496]
  勾配勾配降下法によりトレーニングされたニューラルネットワークが、トレーニング分布の支持の外で学んだことを外挿する方法について検討する。 グラフニューラルネットワーク(GNN)は、より複雑なタスクでいくつかの成功を収めている。
  論文  参考訳（メタデータ） (2020-09-24T17:48:59Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。 回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
  論文  参考訳（メタデータ） (2020-06-25T00:45:52Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。 マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。 マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
  論文  参考訳（メタデータ） (2020-06-15T17:06:17Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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