論文の概要: The Neural-Prediction based Acceleration Algorithm of Column Generation
for Graph-Based Set Covering Problems
- arxiv url: http://arxiv.org/abs/2207.01411v1
- Date: Mon, 4 Jul 2022 13:46:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-05 16:50:58.202443
- Title: The Neural-Prediction based Acceleration Algorithm of Column Generation
for Graph-Based Set Covering Problems
- Title（参考訳）: グラフベース集合被覆問題に対するニューラルネットワークによるカラム生成高速化アルゴリズム
- Authors: Haofeng Yuan, Peng Jiang and Shiji Song
- Abstract要約: グラフに基づく集合被覆問題の解法として,ニューラル予測(CG-P)を用いたカラム生成アルゴリズムを提案する。
グラフニューラルネットワークに基づくニューラル予測モデルを用いて,各エッジの最終解に含まれる確率を予測する。
鉄道員のスケジューリング問題に対するCG-Pアルゴリズムの評価を行い,ベースライン列生成アルゴリズムよりも優れていた。
- 参考スコア（独自算出の注目度）: 20.1479227701035
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Set covering problem is an important class of combinatorial optimization
problems, which has been widely applied and studied in many fields. In this
paper, we propose an improved column generation algorithm with neural
prediction (CG-P) for solving graph-based set covering problems. We leverage a
graph neural network based neural prediction model to predict the probability
to be included in the final solution for each edge. Our CG-P algorithm
constructs a reduced graph that only contains the edges with higher predicted
probability, and this graph reduction process significantly speeds up the
solution process. We evaluate the CG-P algorithm on railway crew scheduling
problems and it outperforms the baseline column generation algorithm. We
provide two solution modes for our CG-P algorithm. In the optimal mode, we can
obtain a solution with an optimality guarantee while reducing the time cost to
63.12%. In the fast mode, we can obtain a sub-optimal solution with a 7.62%
optimality gap in only 2.91% computation time.
- Abstract（参考訳）: 集合被覆問題は組合せ最適化問題の重要なクラスであり、多くの分野で広く適用され研究されている。
本稿では,グラフに基づく集合被覆問題の解法として,ニューラルネットワークを用いたカラム生成アルゴリズムを提案する。
グラフニューラルネットワークに基づくニューラル予測モデルを用いて,各エッジに対する最終解に含まれる確率を予測する。
我々のCG-Pアルゴリズムは、予測確率の高いエッジのみを含む縮小グラフを構築し、このグラフ削減プロセスは解処理を著しく高速化する。
鉄道員のスケジューリング問題に対するCG-Pアルゴリズムの評価を行い,ベースライン列生成アルゴリズムよりも優れていた。
我々はCG-Pアルゴリズムに2つの解モードを提供する。
最適モードでは、時間コストを63.12%に抑えながら最適性を保証する解が得られる。
高速モードでは、わずか2.91%の計算時間で7.62%の最適ギャップを持つ準最適解が得られる。
関連論文リスト
- Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
従来のアルゴリズムの近似保証よりも高い精度で予測を行う。
我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。
この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
論文 参考訳（メタデータ） (2024-11-25T17:31:34Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Are Graph Neural Networks Optimal Approximation Algorithms? [26.5364112420121]
最適化問題のクラスに対して最適な近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。
我々は、OptGNNの学習した埋め込みから最適解のバウンダリを生成するアルゴリズムを設計するために、凸緩和を捕捉するOptGNNの能力を利用する。
論文 参考訳（メタデータ） (2023-10-01T00:12:31Z) - Unfolded proximal neural networks for robust image Gaussian denoising [7.018591019975253]
本稿では,二元FBと二元Chambolle-Pockアルゴリズムの両方に基づいて,ガウス分母タスクのためのPNNを統一的に構築するフレームワークを提案する。
また、これらのアルゴリズムの高速化により、関連するNN層におけるスキップ接続が可能であることを示す。
論文 参考訳（メタデータ） (2023-08-06T15:32:16Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem [0.0]
グラフ燃焼問題の解法として,Centrality BAsed Genetic-algorithm (CBAG) という効率的な遺伝的アルゴリズムを提案する。
グラフバーニング問題の特徴を考慮し,新しい染色体表現法と評価法を提案する。
この結果から,提案アルゴリズムは従来の最先端の中央値と比較して性能が向上していることが明らかとなった。
論文 参考訳（メタデータ） (2022-08-01T17:34:07Z) - Neural Improvement Heuristics for Graph Combinatorial Optimization
Problems [49.85111302670361]
本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。
提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
論文 参考訳（メタデータ） (2022-06-01T10:35:29Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Gumbel-softmax-based Optimization: A Simple General Framework for
Optimization Problems on Graphs [5.486093983007419]
本稿では,ディープラーニングフレームワークによって強化された高度な自動微分技術に基づく,シンプルで高速で汎用的なアルゴリズムフレームワークを提案する。
高品質なソリューションは、従来のアプローチに比べてはるかに少ない時間で得られる。
論文 参考訳（メタデータ） (2020-04-14T14:11:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。