論文の概要: 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%の最適ギャップを持つ準最適解が得られる。
関連論文リスト
- Are Graph Neural Networks Optimal Approximation Algorithms? [28.469481437685072]
最適化問題のクラスに対して最適な近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。
我々は、OptGNNの学習した埋め込みから最適解のバウンダリを生成するアルゴリズムを設計するために、凸緩和を捕捉するOptGNNの能力を利用する。
論文 参考訳(メタデータ) (2023-10-01T00:12:31Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - 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) - Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
本研究は,機械学習を用いて効果的な霊長類を自動学習できるかどうかを考察する。
本稿では,最適化問題をグラフとして表現するための新しい手法を提案する。
可変解の予測はB&B法の新たな構成であるProbabilistic Branching with guided Depth-first Searchによって行われる。
論文 参考訳(メタデータ) (2021-07-02T06:46:23Z) - Improved Acyclicity Reasoning for Bayesian Network Structure Learning
with Constraint Programming [0.0]
離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。
本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。
最適ではないにもかかわらず、性能は桁違いに向上することを示す。
結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
論文 参考訳(メタデータ) (2021-06-23T09:46:11Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。