論文の概要: Controlling Continuous Relaxation for Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2309.16965v1
- Date: Fri, 29 Sep 2023 04:23:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-02 15:39:33.581961
- Title: Controlling Continuous Relaxation for Combinatorial Optimization
- Title（参考訳）: 組合せ最適化のための連続緩和制御
- Authors: Yuma Ichikawa
- Abstract要約: 本論文は,高密度グラフ上のCO問題の早期学習において,PI-GNNソルバがすべての変数がゼロとなる局所解に閉じ込められることを数値的に示す。
次に、局所解を避けながら、緩和変数の連続性と離散性を制御することで、これらの問題に対処する。
実証的には、PI-GNNソルバが妥当な解を見つけるのに苦労する高密度グラフ上のCO問題や、比較的スパースなグラフ上の問題に対してより良い結果が得られる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent advancements in combinatorial optimization (CO) problems emphasize the
potential of graph neural networks (GNNs). The physics-inspired GNN (PI-GNN)
solver, which finds approximate solutions through unsupervised learning, has
attracted significant attention for large-scale CO problems. Nevertheless,
there has been limited discussion on the performance of the PI-GNN solver for
CO problems on relatively dense graphs where the performance of greedy
algorithms worsens. In addition, since the PI-GNN solver employs a relaxation
strategy, an artificial transformation from the continuous space back to the
original discrete space is necessary after learning, potentially undermining
the robustness of the solutions. This paper numerically demonstrates that the
PI-GNN solver can be trapped in a local solution, where all variables are zero,
in the early stage of learning for CO problems on the dense graphs. Then, we
address these problems by controlling the continuity and discreteness of
relaxed variables while avoiding the local solution: (i) introducing a new
penalty term that controls the continuity and discreteness of the relaxed
variables and eliminates the local solution; (ii) proposing a new continuous
relaxation annealing (CRA) strategy. This new annealing first prioritizes
continuous solutions and intensifies exploration by leveraging the continuity
while avoiding the local solution and then schedules the penalty term for
prioritizing a discrete solution until the relaxed variables are almost
discrete values, which eliminates the need for an artificial transformation
from the continuous to the original discrete space. Empirically, better results
are obtained for CO problems on the dense graphs, where the PI-GNN solver
struggles to find reasonable solutions, and for those on relatively sparse
graphs. Furthermore, the computational time scaling is identical to that of the
PI-GNN solver.
- Abstract（参考訳）: 組合せ最適化(CO)問題の最近の進歩は、グラフニューラルネットワーク(GNN)の可能性を強調している。
物理に着想を得た GNN (PI-GNN) ソルバは教師なし学習により近似解を求めるが, 大規模CO問題に注目が集まっている。
それにもかかわらず、比較的高密度なグラフ上でのCO問題に対するPI-GNNソルバの性能に関する限定的な議論がある。
さらに、PI-GNNソルバは緩和戦略を採用しているため、学習後に連続空間から元の離散空間への人工的な変換が必要であり、解の堅牢性を損なう可能性がある。
本論文は,高密度グラフ上のCO問題の早期学習において,PI-GNNソルバがすべての変数がゼロとなる局所解に閉じ込められることを数値的に示す。
次に, 局所解を回避しつつ, 緩和変数の連続性と離散性を制御することにより, これらの問題に対処する。
(i)緩和変数の連続性と離散性を制御し、局所解を排除する新たなペナルティ用語を導入すること。
(II)新しい連続緩和焼鈍(CRA)戦略を提案する。
この新たなアニールは、まず連続解を優先し、局所解を避けながら連続性を活用して探索を強化し、その後、緩和された変数がほぼ離散値になるまで離散解を優先順位付けするためのペナルティ項をスケジュールし、連続から元の離散空間への人工的な変換の必要性を排除した。
実証的には、PI-GNNソルバが妥当な解を見つけるのに苦労するグラフ上のCO問題や比較的スパースなグラフ上の問題に対してより良い結果が得られる。
さらに、計算時間のスケーリングはPI-GNNソルバと同じである。
関連論文リスト
- Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。
数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
論文 参考訳（メタデータ） (2024-09-02T12:55:27Z) - Adaptive Layer Splitting for Wireless LLM Inference in Edge Computing: A Model-Based Reinforcement Learning Approach [18.153641696306707]
本研究では、モデルベース強化学習(MBRL)からインスピレーションを得て、エッジとユーザ機器(UE)間の最適分割点を決定するフレームワークを提案する。
報酬代理モデルを導入することで、頻繁な性能評価の計算コストを大幅に削減できる。
論文 参考訳（メタデータ） (2024-06-03T09:41:42Z) - An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳（メタデータ） (2024-03-11T02:17:42Z) - Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳（メタデータ） (2024-03-06T04:43:22Z) - Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems [0.6906005491572401]
本研究では、教師なし学習(UL)に基づくCOソルバのための連続的アン緩和(CTRA)を提案する。
CTRAは、単一のトレーニング実行で多様なソリューションを見つけるための計算効率のよいフレームワークである。
数値実験により、CTRAにより、ULベースの解法は、既存の解法を繰り返すよりもはるかに高速にこれらの多様な解を見つけることができることが示された。
論文 参考訳（メタデータ） (2024-02-03T15:31:05Z) - Stochastic Unrolled Federated Learning [85.6993263983062]
本稿では,UnRolled Federated Learning (SURF)を導入する。
提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
論文 参考訳（メタデータ） (2023-05-24T17:26:22Z) - Federated Compositional Deep AUC Maximization [58.25078060952361]
本研究では,曲線(AUC)のスコアを直接最適化することにより,不均衡なデータに対する新しいフェデレート学習法を開発した。
私たちの知る限りでは、このような好ましい理論的な結果を達成した最初の作品である。
論文 参考訳（メタデータ） (2023-04-20T05:49:41Z) - Accelerating Federated Edge Learning via Topology Optimization [41.830942005165625]
フェデレートエッジラーニング(FEEL)は、プライバシー保護の分散ラーニングを実現するための有望なパラダイムとして考えられている。
ストラグラー装置の存在により、過度の学習時間を消費する。
フェデレーション学習における不均一性問題に対処するために,新しいトポロジ最適化フェデレーション・エッジ・ラーニング(TOFEL)手法を提案する。
論文 参考訳（メタデータ） (2022-04-01T14:49:55Z) - Learning for Robust Combinatorial Optimization: Algorithm and
Application [26.990988571097827]
最適化学習(L2O)は、ニューラルネットワークの強い予測力を活用することにより、最適化問題を解決するための有望なアプローチとして登場した。
本稿では,不確実な状況下で頑健な解を迅速に出力するLRCOという新しい学習ベース最適化を提案する。
その結果、LRCOは、非常に少ない複雑さで、最悪のケースコストとランタイムを大幅に削減できることがわかった。
論文 参考訳（メタデータ） (2021-12-20T07:58:50Z) - Fast Distributionally Robust Learning with Variance Reduced Min-Max
Optimization [85.84019017587477]
分散的ロバストな教師付き学習は、現実世界のアプリケーションのための信頼性の高い機械学習システムを構築するための重要なパラダイムとして登場している。
Wasserstein DRSLを解くための既存のアルゴリズムは、複雑なサブプロブレムを解くか、勾配を利用するのに失敗する。
我々はmin-max最適化のレンズを通してwaserstein drslを再検討し、スケーラブルで効率的に実装可能な超勾配アルゴリズムを導出する。
論文 参考訳（メタデータ） (2021-04-27T16:56:09Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。