論文の概要: Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2402.02190v2
• Date: Sat, 25 May 2024 04:42:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-29 07:44:38.385097
• Title: Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems
• Title（参考訳）: 組合せ最適化問題における逆解探索のための連続テンソル緩和法
• Authors: Yuma Ichikawa, Hiroaki Iwashita,
• Abstract要約: 本研究では、教師なし学習(UL)に基づくCOソルバのための連続的アン緩和(CTRA)を提案する。 CTRAは、単一のトレーニング実行で多様なソリューションを見つけるための計算効率のよいフレームワークである。 数値実験により、CTRAにより、ULベースの解法は、既存の解法を繰り返すよりもはるかに高速にこれらの多様な解を見つけることができることが示された。
• 参考スコア（独自算出の注目度）: 0.6906005491572401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding the best solution is a common objective in combinatorial optimization (CO). In practice, directly handling constraints is often challenging, incorporating them into the objective function as the penalties. However, balancing these penalties to achieve the desired solution is time-consuming. Additionally, formulated objective functions and constraints often only approximate real-world scenarios, where the optimal solution is not necessarily the best solution for the original real-world problem. One solution is to obtain (i) penalty-diversified solutions with varying penalty strengths for the former issue and (ii) variation-diversified solutions with different characteristics for the latter issue. Users can then post-select the desired solution from these diverse solutions. However, efficiently finding these diverse solutions is more difficult than identifying one. This study introduces Continual Tensor Relaxation Annealing (CTRA) for unsupervised-learning (UL)-based CO solvers, a computationally efficient framework for finding these diverse solutions in a single training run. The key idea is to leverage representation learning capability to automatically and efficiently learn common representations and parallelization. Numerical experiments show that CTRA enables UL-based solvers to find these diverse solutions much faster than repeatedly running existing UL-based solvers.
• Abstract（参考訳）: 最適解を見つけることは組合せ最適化(CO)において共通の目的である。 実際には、直接的に制約を扱うことはしばしば困難であり、それらは罰則として客観的な機能に組み込まれている。 しかし、これらの罰則のバランスが望ましいソリューションを達成するのに時間がかかる。 さらに、定式化された目的関数と制約は、しばしば実世界のシナリオに近似するだけであり、最適解が元の実世界の問題にとって必ずしも最良の解ではない。 一つの解決策は 一 前号の罰則の異なる罰則の解 (II)後者の課題に対する異なる特徴を持つ変分解。 ユーザは、これらの多様なソリューションから、望ましいソリューションをポストセレクトできる。 しかし、これらの多様な解を効率的に見つけることは、それらを特定することよりも難しい。 本研究では,教師なし学習(UL)に基づくCOソルバのための連続的テンソル緩和アニーリング(CTRA)を紹介した。 鍵となる考え方は、表現学習能力を活用して、共通の表現と並列化を自動的にかつ効率的に学習することだ。 数値実験により、CTRAは既存のULベースの解法を繰り返すよりもはるかに高速にこれらの多様な解を見つけることができることが示された。

関連論文リスト

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems [37.205311971072405]
  DISCOは、大規模な組合せ最適化問題に対する効率的な拡散解法である。 サンプリング空間は、解残基によって導かれるより有意義な領域に制約され、出力分布のマルチモーダルな性質は保たれる。 大規模なトラベリングセールスマン問題や最大独立セットのベンチマークに挑戦し、他の拡散手段よりも最大5.28倍の速度で推論を行う。
  論文  参考訳（メタデータ） (2024-06-28T07:36:31Z)
• Improved Training of Physics-Informed Neural Networks with Model Ensembles [81.38804205212425]
  我々は、PINNを正しい解に収束させるため、解区間を徐々に拡大することを提案する。 すべてのアンサンブルのメンバーは、観測されたデータの近くで同じ解に収束する。 提案手法は, 得られた解の精度を向上させることができることを示す。
  論文  参考訳（メタデータ） (2022-04-11T14:05:34Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• A Mutual Information Maximization Approach for the Spurious Solution Problem in Weakly Supervised Question Answering [60.768146126094955]
  弱々しい教師付き質問応答は通常、最終的な答えのみを監督信号として持つ。 偶然に正解を導出する刺激的な解が多数存在するかもしれないが、そのような解の訓練はモデルの性能を損なう可能性がある。 本稿では,質問応答対と予測解間の相互情報の最大化により,このような意味的相関を明示的に活用することを提案する。
  論文  参考訳（メタデータ） (2021-06-14T05:47:41Z)
• Discovering Diverse Solutions in Deep Reinforcement Learning [84.45686627019408]
  強化学習アルゴリズムは通常、特定のタスクの単一のソリューションを学ぶことに限定される。 連続的あるいは離散的な低次元潜在変数に条件付きポリシーを訓練することにより、無限に多くの解を学習できるRL法を提案する。
  論文  参考訳（メタデータ） (2021-03-12T04:54:31Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。 最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
  論文  参考訳（メタデータ） (2021-02-14T18:05:42Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。