論文の概要: Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2310.07979v1
- Date: Thu, 12 Oct 2023 01:57:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-15 11:33:45.703098
- Title: Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks
- Title(参考訳): Graph-SCP: グラフニューラルネットワークによる集合被覆問題の高速化
- Authors: Zohair Shafi, Benjamin A. Miller, Tina Eliassi-Rad, Rajmonda S.
Caceres
- Abstract要約: グラフニューラルネットワークは、解空間を含むはるかに小さなサブプロブレムを識別することを学ぶことで、既存の最適化問題を増大させることができる。
また,Graph-SCPは,市販の解法に比べて30~70%削減し,実行時間を25倍に高速化することを示した。
Graph-SCPは、より大きな問題サイズに一般化することができ、他のML拡張COソルバと併用することで、さらなる実行時間の改善につながる可能性がある。
- 参考スコア(独自算出の注目度): 1.4497190759588077
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Machine learning (ML) approaches are increasingly being used to accelerate
combinatorial optimization (CO) problems. We look specifically at the Set Cover
Problem (SCP) and propose Graph-SCP, a graph neural network method that can
augment existing optimization solvers by learning to identify a much smaller
sub-problem that contains the solution space. We evaluate the performance of
Graph-SCP on synthetic weighted and unweighted SCP instances with diverse
problem characteristics and complexities, and on instances from the OR Library,
a canonical benchmark for SCP. We show that Graph-SCP reduces the problem size
by 30-70% and achieves run time speedups up to~25x when compared to commercial
solvers (Gurobi). Given a desired optimality threshold, Graph-SCP will improve
upon it or even achieve 100% optimality. This is in contrast to fast greedy
solutions that significantly compromise solution quality to achieve guaranteed
polynomial run time. Graph-SCP can generalize to larger problem sizes and can
be used with other conventional or ML-augmented CO solvers to lead to potential
additional run time improvement.
- Abstract(参考訳): 機械学習(ML)アプローチは、組合せ最適化(CO)問題を加速するためにますます利用されている。
本稿では,SCP(Set Cover Problem)を特に検討し,解空間を含むより小さなサブプロブレムの同定を学習することにより,既存の最適化問題を拡張可能なグラフニューラルネットワークであるGraph-SCPを提案する。
合成重み付きおよび非重み付きSCPインスタンスにおけるGraph-SCPの性能と,SCPの標準ベンチマークであるOR Libraryの事例について検討した。
本稿では,Graph-SCP が問題サイズを 30-70% 削減し,商用解法 (Gurobi) と比較して実行時間を最大25倍に高速化することを示す。
望ましい最適性しきい値が与えられると、Graph-SCPはそれを改善するか、100%最適性を達成する。
これは、多項式実行時間を保証するために、ソリューションの品質を著しく損なう高速な欲望ソリューションとは対照的である。
Graph-SCPはより大きな問題サイズに一般化することができ、他のML拡張COソルバと併用することで、さらなる実行時間の改善につながる可能性がある。
関連論文リスト
- Symmetry-preserving graph attention network to solve routing problems at
multiple resolutions [1.9304772860080408]
問題解決のために,最初の完全同変モデルとトレーニングを導入する。
入力グラフのマルチスケール構造を捉えることが不可欠である。
本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
論文 参考訳(メタデータ) (2023-10-24T06:22:20Z) - GRASP: Accelerating Shortest Path Attacks via Graph Attention [1.3270612461223892]
機械学習(ML)の最近の進歩は、古典的な最適化アルゴリズムの補助と加速を約束している。
本稿では,GRASPアルゴリズムを提案する。 Graph Accelerated Shortest Path Attackは,実行時間を最大10倍高速化するML支援最適化アルゴリズムである。
論文 参考訳(メタデータ) (2023-10-12T02:03:10Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳(メタデータ) (2023-05-26T15:13:09Z) - Learning to Solve Combinatorial Graph Partitioning Problems via
Efficient Exploration [72.15369769265398]
実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。
最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
論文 参考訳(メタデータ) (2022-05-27T17:13:10Z) - LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale
Combinatorial Optimisation [6.316693022958222]
ユークリッド部分グラフの埋め込みを地図として用いて,可能な部分グラフの空間をナビゲートする方法を学習する強化学習アルゴリズムを提案する。
LeNSEは、グラフ全体への埋め込みの実行によって見いだされたソリューションに匹敵するソリューションをもたらす小さなサブグラフを識別するが、全体の実行時間のごく一部にはならない。
論文 参考訳(メタデータ) (2022-05-20T11:54:03Z) - Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted
Graph Convolutional Neural Networks [13.985534521589257]
グラフ畳み込みニューラルネットワーク(GNN)は、最適化の文脈で有望であることが証明されている。
我々は、グラフ畳み込みネットワーク、符号付きグラフ畳み込みネットワーク、グラフ等化ネットワークなど、さまざまなGNNに適応する。
エンドツーエンドのトレーニング可能なマルチカットへの最初のアプローチを提供する。
論文 参考訳(メタデータ) (2022-04-04T10:21:02Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳(メタデータ) (2022-01-06T21:02:30Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳(メタデータ) (2021-06-09T09:18:18Z) - Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
本稿では,従来のグラフ信号フィルタリングと深い特徴学習を併用して,競合するハイブリッド設計を提案する。
解釈可能な低パスグラフフィルタを用い、最先端のDL復調方式DnCNNよりも80%少ないネットワークパラメータを用いる。
論文 参考訳(メタデータ) (2020-10-21T20:04:22Z) - Fast Convex Relaxations using Graph Discretizations [13.977100716044102]
マッチングと視覚問題はコンピュータ・コンピューティング・アプリケーションの基本である。
応用技術は、実用的な応用においてその実現可能性を減らすための重要な計算努力が伴う。
このセットアップにより、SLICやCut-Pursuitによって構築された問題に忠実に取り組むことができます。
論文 参考訳(メタデータ) (2020-04-23T11:14:38Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳(メタデータ) (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。