論文の概要: Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems

• arxiv url: http://arxiv.org/abs/2310.10603v1
• Date: Mon, 16 Oct 2023 17:31:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-17 12:37:56.707222
• Title: Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems
• Title（参考訳）: 線形最適化問題の解法におけるグラフニューラルネットワークのパワーの探索
• Authors: Chendi Qian, Didier Ch\'etelat, Christopher Morris
• Abstract要約: グラフニューラルネットワーク(MPNN)は、混合整数最適化問題を高速化する。 線形最適化をエミュレートするMPNNの有効性はほとんど不明である。 線形最適化問題を解くための軽量プロキシとしてMPNNがどのように機能するかを強調した。
• 参考スコア（独自算出の注目度）: 5.966097889241178
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, machine learning, particularly message-passing graph neural networks (MPNNs), has gained traction in enhancing exact optimization algorithms. For example, MPNNs speed up solving mixed-integer optimization problems by imitating computational intensive heuristics like strong branching, which entails solving multiple linear optimization problems (LPs). Despite the empirical success, the reasons behind MPNNs' effectiveness in emulating linear optimization remain largely unclear. Here, we show that MPNNs can simulate standard interior-point methods for LPs, explaining their practical success. Furthermore, we highlight how MPNNs can serve as a lightweight proxy for solving LPs, adapting to a given problem instance distribution. Empirically, we show that MPNNs solve LP relaxations of standard combinatorial optimization problems close to optimality, often surpassing conventional solvers and competing approaches in solving time.
• Abstract（参考訳）: 近年、機械学習、特にメッセージパスグラフニューラルネットワーク(MPNN)は、正確な最適化アルゴリズムの強化で注目を集めている。 例えばmpnnは、強分岐のような計算集約的なヒューリスティックを模倣し、多重線形最適化問題(lps)の解決を高速化する。 経験的成功にもかかわらず、線形最適化をエミュレートするMPNNの有効性の背景には、大半が明確でない。 本稿では,MPNNがLPの標準的なインテリアポイント法をシミュレートし,その実用的成功を説明する。 さらに、MPNNがLPを解くための軽量プロキシとして機能し、与えられた問題インスタンスの分布に適応する方法について強調する。 経験的に、MPNNは、最適性に近い標準組合せ最適化問題のLP緩和を解き、従来の解法や競合する解法を超越することが多い。

関連論文リスト

• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Reducing the Need for Backpropagation and Discovering Better Optima With Explicit Optimizations of Neural Networks [4.807347156077897]
  本稿では,ニューラルネットワークの最適化のための計算効率のよい代替案を提案する。 我々は、単純なフィードフォワード言語モデルに対する明確な解決策を導出する。 実験では,明示的な解がほぼ最適であることを示す。
  論文  参考訳（メタデータ） (2023-11-13T17:38:07Z)
• An Expandable Machine Learning-Optimization Framework to Sequential Decision-Making [0.0]
  逐次的意思決定問題を効率的に解決する統合予測最適化(PredOpt)フレームワークを提案する。 本稿では,機械学習(ML)における逐次依存,実現可能性,一般化といった課題に対処し,インスタンス問題に対する最適解の予測を行う。
  論文  参考訳（メタデータ） (2023-11-12T21:54:53Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。 MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
  論文  参考訳（メタデータ） (2023-09-02T11:01:16Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• On Representing Linear Programs by Graph Neural Networks [30.998508318941017]
  グラフニューラルネットワーク(GNN)は最適化問題に適した機械学習モデルであると考えられている。 本稿では,線形プログラム(LP)問題にGNNを適用する理論的基礎を確立する。 適切に構築されたGNNは、幅広いクラスにおける各LPに対して、実現可能性、有界性、最適解を確実に予測できることを示す。
  論文  参考訳（メタデータ） (2022-09-25T18:27:33Z)
• Recurrent Bilinear Optimization for Binary Neural Networks [58.972212365275595]
  BNNは、実数値重みとスケールファクターの内在的双線型関係を無視している。 私たちの仕事は、双線形の観点からBNNを最適化する最初の試みです。 我々は、様々なモデルやデータセット上で最先端のBNNに対して印象的な性能を示す頑健なRBONNを得る。
  論文  参考訳（メタデータ） (2022-09-04T06:45:33Z)
• Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks [13.985534521589257]
  グラフ畳み込みニューラルネットワーク(GNN)は、最適化の文脈で有望であることが証明されている。 我々は、グラフ畳み込みネットワーク、符号付きグラフ畳み込みネットワーク、グラフ等化ネットワークなど、さまざまなGNNに適応する。 エンドツーエンドのトレーニング可能なマルチカットへの最初のアプローチを提供する。
  論文  参考訳（メタデータ） (2022-04-04T10:21:02Z)
• Learning from Images: Proactive Caching with Parallel Convolutional Neural Networks [94.85780721466816]
  本稿では,プロアクティブキャッシングのための新しいフレームワークを提案する。 モデルベースの最適化とデータ駆動技術を組み合わせて、最適化問題をグレースケールのイメージに変換する。 数値計算の結果,提案手法は71.6%の計算時間を0.8%のコストで削減できることがわかった。
  論文  参考訳（メタデータ） (2021-08-15T21:32:47Z)
• Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
  自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。 本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。 その結果, 直接使用法と比較して計算時間を2～5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
  論文  参考訳（メタデータ） (2020-02-04T20:00:28Z)

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

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