論文の概要: DOGE-Train: Discrete Optimization on GPU with End-to-end Training

• arxiv url: http://arxiv.org/abs/2205.11638v1
• Date: Mon, 23 May 2022 21:09:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-25 15:23:09.483479
• Title: DOGE-Train: Discrete Optimization on GPU with End-to-end Training
• Title（参考訳）: DOGE-Train: エンドツーエンドトレーニングによるGPUの離散最適化
• Authors: Ahmed Abbas, Paul Swoboda
• Abstract要約: グラフニューラルネットワークを用いて,0-1整数線形プログラムの線形緩和を高速かつスケーラブルに解く手法を提案する。 我々の解法はラグランジュ分解に基づくアルゴリズムFastDOGに基づいている。
• 参考スコア（独自算出の注目度）: 20.254912065749956
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a fast, scalable, data-driven approach for solving linear relaxations of 0-1 integer linear programs using a graph neural network. Our solver is based on the Lagrange decomposition based algorithm FastDOG (Abbas et al. (2022)). We make the algorithm differentiable and perform backpropagation through the dual update scheme for end-to-end training of its algorithmic parameters. This allows to preserve the algorithm's theoretical properties including feasibility and guaranteed non-decrease in the lower bound. Since FastDOG can get stuck in suboptimal fixed points, we provide additional freedom to our graph neural network to predict non-parametric update steps for escaping such points while maintaining dual feasibility. For training of the graph neural network we use an unsupervised loss and perform experiments on large-scale real world datasets. We train on smaller problems and test on larger ones showing strong generalization performance with a graph neural network comprising only around 10k parameters. Our solver achieves significantly faster performance and better dual objectives than its non-learned version. In comparison to commercial solvers our learned solver achieves close to optimal objective values of LP relaxations and is faster by up to an order of magnitude on very large problems from structured prediction and on selected combinatorial optimization problems.
• Abstract（参考訳）: グラフニューラルネットワークを用いて,0-1整数線形プログラムの線形緩和を高速かつスケーラブルに解く手法を提案する。 我々の解法はラグランジュ分解に基づくアルゴリズムFastDOG(Abbas et al. (2022))に基づいている。 アルゴリズムを微分可能とし、アルゴリズムパラメータのエンドツーエンドトレーニングのためのデュアルアップデートスキームを通じてバックプロパゲーションを行う。 これにより、実現可能性や下限での非決定性を含むアルゴリズムの理論的性質を保存できる。 FastDOGは最適以下の固定点で立ち往生できるため、グラフニューラルネットワークにさらなる自由を与え、そのような点を回避し、二重実現可能性を維持しながら、非パラメトリックな更新ステップを予測する。 グラフニューラルネットワークのトレーニングには、教師なしの損失を使用し、大規模な実世界データセットで実験を行います。 約10kのパラメータからなるグラフニューラルネットワークを用いて,より小さな問題を学習し,強力な一般化性能を示す。 我々の解法は、非学習版よりも性能が大幅に向上し、二重目的が向上する。 商用解法と比較すると,lp緩和の最適目的値に近い値が得られ,構造的予測や選択された組合せ最適化問題など,非常に大きな問題に対して最大1桁の速度で解法が実現される。

関連論文リスト

• Newton Losses: Using Curvature Information for Learning with Differentiable Algorithms [80.37846867546517]
  カスタム目的の8つの異なるニューラルネットワークのトレーニング方法を示す。 我々はその2次情報を経験的フィッシャー行列を通して活用する。 ロスロスロスシブルアルゴリズムを用いて、少ない微分可能アルゴリズムに対する大幅な改善を実現する。
  論文  参考訳（メタデータ） (2024-10-24T18:02:11Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。 実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-10-05T02:58:29Z)
• Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning [39.40838358438744]
  線形プログラム(ILP)は、多数の最適化問題のモデリングと解決のための強力なツールである。 アルゴリズムとしてLarge Neighborhood Search (LNS)は、ブランチやバウンドよりも高速に、ILPの高品質なソリューションを見つけることができる。 本稿では,メトリクスによって測定された複数のILPベンチマークに対して,最先端のリアルタイム性能を実現する新しいアプローチCL-LNSを提案する。
  論文  参考訳（メタデータ） (2023-02-03T07:15:37Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
  論文  参考訳（メタデータ） (2023-01-24T12:01:45Z)
• On Representing Linear Programs by Graph Neural Networks [30.998508318941017]
  グラフニューラルネットワーク(GNN)は最適化問題に適した機械学習モデルであると考えられている。 本稿では,線形プログラム(LP)問題にGNNを適用する理論的基礎を確立する。 適切に構築されたGNNは、幅広いクラスにおける各LPに対して、実現可能性、有界性、最適解を確実に予測できることを示す。
  論文  参考訳（メタデータ） (2022-09-25T18:27:33Z)
• Fast Graph Learning with Unique Optimal Solutions [31.411988486916545]
  既知のクローズドフォームソリューションで対流目標を最適化する効率的なGLL法を提案します。 提案手法は, GRLタスクにおける競合性能や最新性能を実現する。
  論文  参考訳（メタデータ） (2021-02-17T02:00:07Z)
• Hybrid Models for Learning to Branch [81.93868699246214]
  我々はCPUマシン上で効率的な分岐を行うための新しいハイブリッドアーキテクチャを提案する。 提案アーキテクチャは,GNNの表現力と分岐処理のための計算コストの低い多層パーセプトロン(MLP)を組み合わせる。
  論文  参考訳（メタデータ） (2020-06-26T21:03:45Z)
• Learning to Optimize Non-Rigid Tracking [54.94145312763044]
  我々は、堅牢性を改善し、解法収束を高速化するために学習可能な最適化を採用する。 まず、CNNを通じてエンドツーエンドに学習された深い特徴にアライメントデータ項を統合することにより、追跡対象をアップグレードする。 次に,プレコンディショニング手法と学習手法のギャップを,プレコンディショナを生成するためにトレーニングされたConditionNetを導入することで埋める。
  論文  参考訳（メタデータ） (2020-03-27T04:40:57Z)
• Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
  自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。 本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。 その結果, 直接使用法と比較して計算時間を2～5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
  論文  参考訳（メタデータ） (2020-02-04T20:00:28Z)

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

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