論文の概要: Hybrid Models for Learning to Branch

• arxiv url: http://arxiv.org/abs/2006.15212v3
• Date: Fri, 23 Oct 2020 14:01:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-16 21:40:47.910284
• Title: Hybrid Models for Learning to Branch
• Title（参考訳）: 分岐学習のためのハイブリッドモデル
• Authors: Prateek Gupta, Maxime Gasse, Elias B. Khalil, M. Pawan Kumar, Andrea Lodi, Yoshua Bengio
• Abstract要約: 我々はCPUマシン上で効率的な分岐を行うための新しいハイブリッドアーキテクチャを提案する。 提案アーキテクチャは,GNNの表現力と分岐処理のための計算コストの低い多層パーセプトロン(MLP)を組み合わせる。
• 参考スコア（独自算出の注目度）: 81.93868699246214
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent Graph Neural Network (GNN) approach for learning to branch has been shown to successfully reduce the running time of branch-and-bound algorithms for Mixed Integer Linear Programming (MILP). While the GNN relies on a GPU for inference, MILP solvers are purely CPU-based. This severely limits its application as many practitioners may not have access to high-end GPUs. In this work, we ask two key questions. First, in a more realistic setting where only a CPU is available, is the GNN model still competitive? Second, can we devise an alternate computationally inexpensive model that retains the predictive power of the GNN architecture? We answer the first question in the negative, and address the second question by proposing a new hybrid architecture for efficient branching on CPU machines. The proposed architecture combines the expressive power of GNNs with computationally inexpensive multi-layer perceptrons (MLP) for branching. We evaluate our methods on four classes of MILP problems, and show that they lead to up to 26% reduction in solver running time compared to state-of-the-art methods without a GPU, while extrapolating to harder problems than it was trained on. The code for this project is publicly available at https://github.com/pg2455/Hybrid-learn2branch.
• Abstract（参考訳）: 分岐学習のための最近のグラフニューラルネットワーク(GNN)アプローチは、MILP(Mixed Integer Linear Programming)のための分岐とバウンドのアルゴリズムの実行時間をうまく削減できることが示されている。 GNNはGPUに依存しているが、MILPソルバは純粋にCPUベースである。 これにより、多くの実践者がハイエンドGPUにアクセスできないため、アプリケーションは非常に制限される。 この作業では、2つの重要な質問をします。 まず、CPUのみが利用可能なより現実的な環境では、GNNモデルは依然として競争力がありますか? 第二に、GNNアーキテクチャの予測能力を保持する計算コストの代替モデルを考案できるだろうか? 我々は、負の質問の最初の質問に答え、CPUマシン上の効率的な分岐のための新しいハイブリッドアーキテクチャを提案する。 提案アーキテクチャは,GNNの表現力と分岐処理のための計算コストの低い多層パーセプトロン(MLP)を組み合わせる。 提案手法をMILP問題の4つのクラスで評価し,GPUのない最先端の手法と比較して最大26%の解法実行時間を短縮できることを示した。 このプロジェクトのコードはhttps://github.com/pg2455/hybrid-learn2branchで公開されている。

関連論文リスト

• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である 本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。 提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
  論文  参考訳（メタデータ） (2022-10-14T03:43:05Z)
• MLPInit: Embarrassingly Simple GNN Training Acceleration with MLP Initialization [51.76758674012744]
  大きなグラフ上でグラフニューラルネットワーク(GNN)をトレーニングするのは複雑で、非常に時間がかかる。 我々は、PeerInitと呼ばれるGNNトレーニングアクセラレーションに対して、恥ずかしく単純だが非常に効果的な方法を提案する。
  論文  参考訳（メタデータ） (2022-09-30T21:33:51Z)
• An efficient and flexible inference system for serving heterogeneous ensembles of deep neural networks [0.0]
  ディープニューラルネットワーク(DNN)のアンサンブルは定性的予測を達成しているが、それらは計算とメモリ集約である。 DNNの柔軟性と効率性を両立させる新しいソフトウェア層を提案する。
  論文  参考訳（メタデータ） (2022-08-30T08:05:43Z)
• DOGE-Train: Discrete Optimization on GPU with End-to-end Training [28.795080637690095]
  0-1整数線形プログラムの緩和を解くために,高速でスケーラブルなデータ駆動型手法を提案する。 グラフニューラルネットワーク(GNN)とラグランジュ分解に基づくアルゴリズムであるFastDOGを用いる。
  論文  参考訳（メタデータ） (2022-05-23T21:09:41Z)
• A Unified Lottery Ticket Hypothesis for Graph Neural Networks [82.31087406264437]
  本稿では,グラフ隣接行列とモデルの重み付けを同時に行う統一GNNスペーシフィケーション(UGS)フレームワークを提案する。 グラフ宝くじ(GLT)をコアサブデータセットとスパースサブネットワークのペアとして定義することにより、人気のある宝くじチケット仮説を初めてGNNsにさらに一般化します。
  論文  参考訳（メタデータ） (2021-02-12T21:52:43Z)
• PyTorch-Direct: Enabling GPU Centric Data Access for Very Large Graph Neural Network Training with Irregular Accesses [19.2129567657739]
  グラフニューラルネットワーク(GNN)トレーニングのためのGPU中心のデータアクセスパラダイムを可能にするPyTorch-Directを紹介します。 マイクロベンチマークとエンドツーエンドのGNNトレーニングの結果から,PyTorch-Directはデータ転送時間を平均47.1%削減し,GNNトレーニングを最大1.6倍高速化した。
  論文  参考訳（メタデータ） (2021-01-20T04:24:39Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。 驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
  論文  参考訳（メタデータ） (2020-04-16T16:20:53Z)
• GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
  検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。 このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。 我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
  論文  参考訳（メタデータ） (2020-02-08T10:03:40Z)

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

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