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

• arxiv url: http://arxiv.org/abs/2402.02190v3
• Date: Thu, 14 Aug 2025 12:55:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-15 22:24:47.943625
• Title: Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems
• Title（参考訳）: 組合せ最適化問題における逆解探索のための連続並列緩和法
• Authors: Yuma Ichikawa, Hiroaki Iwashita,
• Abstract要約: 最適解を見つけることが、しばしば最適化(CO)の主要な目標である。 本研究では、教師なし学習(UL)に基づくCOソルバのための計算効率の高いフレームワークであるCPRA(Continuous Parallel Relaxation Annealing)を紹介する。
• 参考スコア（独自算出の注目度）: 0.6906005491572401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding the optimal solution is often the primary goal in combinatorial optimization (CO). However, real-world applications frequently require diverse solutions rather than a single optimum, particularly in two key scenarios. The first scenario occurs in real-world applications where strictly enforcing every constraint is neither necessary nor desirable. Allowing minor constraint violations can often lead to more cost-effective solutions. This is typically achieved by incorporating the constraints as penalty terms in the objective function, which requires careful tuning of penalty parameters. The second scenario involves cases where CO formulations tend to oversimplify complex real-world factors, such as domain knowledge, implicit trade-offs, or ethical considerations. To address these challenges, generating (i) penalty-diversified solutions by varying penalty intensities and (ii) variation-diversified solutions with distinct structural characteristics provides valuable insights, enabling practitioners to post-select the most suitable solution for their specific needs. However, efficiently discovering these diverse solutions is more challenging than finding a single optimal one. This study introduces Continual Parallel Relaxation Annealing (CPRA), a computationally efficient framework for unsupervised-learning (UL)-based CO solvers that generates diverse solutions within a single training run. CPRA leverages representation learning and parallelization to automatically discover shared representations, substantially accelerating the search for these diverse solutions. Numerical experiments demonstrate that CPRA outperforms existing UL-based solvers in generating these diverse solutions while significantly reducing computational costs.
• Abstract（参考訳）: 最適解を見つけることが組合せ最適化(CO)の主要な目標であることが多い。 しかし、現実世界のアプリケーションは、特に2つの主要なシナリオにおいて、単一の最適化よりも多様なソリューションを必要とすることが多い。 最初のシナリオは、すべての制約を厳格に強制する現実世界のアプリケーションで発生します。 わずかな制約違反を認めることは、しばしばよりコスト効率の良いソリューションにつながる。 これは典型的には、制約を目的関数にペナルティ項として組み込むことによって達成される。 第2のシナリオは、COの定式化がドメイン知識や暗黙のトレードオフ、倫理的考慮といった複雑な現実世界の要素を単純化する傾向にある場合である。 これらの課題に対処し 一 罰則の度合による罰則の多様化 (II) 異なる構造特性を持つ多様なソリューションは、実践者が特定のニーズに対して最も適したソリューションをポストセレクトできる貴重な洞察を提供する。 しかし、これらの多様な解を効率的に発見することは、一つの最適な解を見つけるよりも難しい。 本研究では,教師なし学習(UL)に基づくCOソルバのための計算効率の高いフレームワークであるCPRA(Continuous Parallel Relaxation Annealing)を紹介する。 CPRAは表現学習と並列化を活用し、共有表現を自動的に発見し、これらの多様な解の探索を大幅に加速する。 数値実験により、CPRAは、計算コストを大幅に削減しつつ、これらの多様な解を生成する際に、既存のULベースの解法よりも優れていることを示した。

関連論文リスト

• FSNet: Feasibility-Seeking Neural Network for Constrained Optimization with Guarantees [3.345575993695074]
  伝統的な解法は、しばしばリアルタイムの使用に対して計算的に禁止される。 機械学習ベースのアプローチが代替手段として登場したが、厳格に制約を強制することに苦労している。 制約満足度を確保するためにFSNet(Feasibility-Seeking-Integrated Network)を提案する。
  論文  参考訳（メタデータ） (2025-05-31T03:05:29Z)
• RL-MILP Solver: A Reinforcement Learning Approach for Solving Mixed-Integer Linear Programs with Graph Neural Networks [3.3894236476098185]
  混合整数線形プログラミング (MILP) は様々な分野にまたがる最適化手法である。 本稿では,最初の実現可能な解を見つけるだけでなく,より有効な解を段階的に発見する新しい強化学習(RL)に基づく解法を提案する。
  論文  参考訳（メタデータ） (2024-11-29T07:23:34Z)
• 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)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• 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)

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

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