論文の概要: Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2310.07979v2
- Date: Mon, 26 Aug 2024 15:51:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-28 00:57:20.356152
- 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は、ソリューション空間を含むはるかに小さなサブプロブレムを識別することを学ぶことで、既存の最適化解法を強化するグラフニューラルネットワーク手法である。
グラフ-SCPは問題サイズを60～80%削減し,実行速度を平均10倍に向上することを示す。
Graph-SCPのより大きな問題サイズへの一般化能力、3000サブセットのSCPインスタンスでのトレーニング、最大10,000サブセットのSCPインスタンスでのテストについて紹介する。
- 参考スコア（独自算出の注目度）: 1.3270612461223892
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Machine learning (ML) approaches are increasingly being used to accelerate combinatorial optimization (CO) problems. We investigate the Set Cover Problem (SCP) and propose Graph-SCP, a graph neural network method that augments existing optimization solvers by learning to identify a much smaller sub-problem that contains the solution space. Graph-SCP uses both supervised learning from prior solved instances and unsupervised learning aimed at minimizing the SCP objective. We evaluate the performance of Graph-SCP on synthetically 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 60-80% and achieves runtime speedups of up to 10x on average when compared to Gurobi (a state-of-the-art commercial solver), while maintaining solution quality. This is in contrast to fast greedy solutions that significantly compromise solution quality to achieve guaranteed polynomial runtime. We showcase Graph-SCP's ability to generalize to larger problem sizes, training on SCP instances with up to 3,000 subsets and testing on SCP instances with up to 10,000 subsets.
- Abstract（参考訳）: 機械学習(ML)アプローチは、組合せ最適化(CO)問題を加速するためにますます利用されている。
本稿では,SCP(Set Cover Problem)について検討し,解空間を含むより小さなサブプロブレムを同定し,既存の最適化解法を強化するグラフニューラルネットワークであるGraph-SCPを提案する。
Graph-SCPは、事前に解決されたインスタンスからの教師あり学習と、SCPの目的を最小化することを目的とした教師なし学習の両方を使用する。
合成重み付きおよび非重み付きSCPインスタンスにおけるGraph-SCPの性能と,SCPの標準ベンチマークであるOR Libraryの事例について検討した。
我々は,Graph-SCPが問題サイズを60～80%削減し,ソリューションの品質を維持しつつ,Gurobi(最先端の商用解法)と比較して平均10倍のランタイム高速化を実現していることを示す。
これは、保証多項式ランタイムを達成するために、解の品質を著しく損なう高速な欲求解とは対照的である。
最大3000のサブセットを持つSCPインスタンスでトレーニングし、最大10,000のサブセットを持つSCPインスタンスでテストする。
関連論文リスト
- Symmetry-preserving graph attention network to solve routing problems at
multiple resolutions [1.9304772860080408]
問題解決のために,最初の完全同変モデルとトレーニングを導入する。
入力グラフのマルチスケール構造を捉えることが不可欠である。
本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
論文 参考訳（メタデータ） (2023-10-24T06:22:20Z) - An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling
Problems Based on Constraint Programming [5.070542698701157]
本稿では,CPと強化学習(Reinforcement Learning, RL)を用いてスケジューリング問題を解決する新しいエンドツーエンドアプローチを提案する。
当社のアプローチでは,既存のCPソルバを活用して,プライオリティ・ディスパッチ・ルール(PDR)を学ぶエージェントをトレーニングする。
論文 参考訳（メタデータ） (2023-06-09T08:24:56Z) - 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 Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳（メタデータ） (2022-10-31T09:46:26Z) - 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) - Hybrid ICP [8.57914821832517]
ハイブリッドICPは、オブジェクトのライブイメージに基づいて、データアソシエーション法とエラーメトリックの両方を動的に最適化する。
オブジェクトポーズ推定に使用する場合、ハイブリッドICPは、他のよく使われるICP変種よりも正確で、ノイズに対して頑健であることを示す。
論文 参考訳（メタデータ） (2021-09-15T20:17:11Z) - Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Minimax
Problems [80.46370778277186]
大規模凸凹型ミニマックス問題は、ゲーム理論、堅牢なトレーニング、生成的敵ネットワークのトレーニングなど、多くの応用で発生する。
通信効率のよい分散外グレードアルゴリズムであるLocalAdaSientを開発した。
サーバモデル。
等質な環境と異質な環境の両方において,その有効性を実証する。
論文 参考訳（メタデータ） (2021-06-18T09:42:05Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - Exact Optimization of Conformal Predictors via Incremental and
Decremental Learning [46.9970555048259]
Conformal Predictors (CP) はMLメソッドのラッパーであり、データ分散に対する弱い仮定の下でエラー保証を提供する。
分類や回帰から異常検出まで幅広い問題に適している。
本研究では,基礎となるML手法と組み合わせて学習し,漸進的・漸進的学習を活用することにより,CP分類器を著しく高速化できることを示す。
論文 参考訳（メタデータ） (2021-02-05T15:31:37Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳（メタデータ） (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。