論文の概要: Improving Constraint Satisfaction Algorithm Efficiency for the AllDifferent Constraint

• arxiv url: http://arxiv.org/abs/2012.03624v2
• Date: Sun, 13 Dec 2020 09:59:33 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-16 21:28:03.891200
• Title: Improving Constraint Satisfaction Algorithm Efficiency for the AllDifferent Constraint
• Title（参考訳）: すべての制約に対する制約満足度アルゴリズム効率の向上
• Authors: Geoff Harris
• Abstract要約: 制約満足問題(CSP: Constraint Satisfaction Problems)と記載された組合せ問題を検討する。 元のCSP用に設計され、AllDifferent制約を含む任意のアルゴリズムは、元のCSPと補完的な問題の両方に同時に適用した場合、少なくとも同じレベルの有効性を持つことを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Combinatorial problems stated as Constraint Satisfaction Problems (CSP) are examined. It is shown by example that any algorithm designed for the original CSP, and involving the AllDifferent constraint, has at least the same level of efficacy when simultaneously applied to both the original and its complementary problem. The 1-to-1 mapping employed to transform a CSP to its complementary problem, which is also a CSP, is introduced. This "Dual CSP" method and its application are outlined. The analysis of several random problem instances demonstrate the benefits of this method for variable domain reduction compared to the standard approach to CSP. Extensions to additional constraints other than AllDifferent, as well as the use of hybrid algorithms, are proposed as candidates for this Dual CSP method.
• Abstract（参考訳）: 制約満足度問題 (Constraint Satisfaction Problems, CSP) と呼ばれる組合せ問題について検討した。 例えば、元のCSP用に設計され、AllDifferent制約を含むアルゴリズムは、元のCSPと補完的な問題の両方に同時に適用した場合、少なくとも同じレベルの有効性を持つ。 CSPを補問題に変換するために使用される1-to-1マッピングも導入されている。 この「Dual CSP」法とその応用について概説する。 いくつかのランダムな問題事例の解析は、CSPに対する標準的なアプローチと比較して、変数領域還元に対するこの手法の利点を示している。 alldifferent以外の追加の制約への拡張、およびハイブリッドアルゴリズムの使用は、この双対 csp 法の候補として提案されている。

関連論文リスト

• A Double Tracking Method for Optimization with Decentralized Generalized Orthogonality Constraints [4.6796315389639815]
  分散最適化問題は分散制約の存在下では解決できない。 目的関数の勾配と制約写像のヤコビアンを同時に追跡する新しいアルゴリズムを導入する。 合成と実世界の両方のデータセットに数値的な結果を示す。
  論文  参考訳（メタデータ） (2024-09-08T06:57:35Z)
• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  我々はC-PGと呼ばれる探索非依存のアルゴリズムを導入し、このアルゴリズムは(弱)勾配支配仮定の下でのグローバルな最終点収束を保証する。 制約付き制御問題に対して,我々のアルゴリズムを数値的に検証し,それらを最先端のベースラインと比較する。
  論文  参考訳（メタデータ） (2024-07-15T14:54:57Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。 この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。 次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
  論文  参考訳（メタデータ） (2022-01-21T04:25:35Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• A Hybrid APM-CPGSO Approach for Constraint Satisfaction Problem Solving: Application to Remote Sensing [2.6641834518599308]
  制約満足度問題(CSP)は、様々な複雑な実世界の問題のモデル化と解決に積極的に用いられている。 既存の問題解決手法は、ほとんどの場合不適当である。 本稿では,問題解決のための不完全なCSP法と完全CSP法を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-06-06T22:05:22Z)
• Sample-based Federated Learning via Mini-batch SSCA [18.11773963976481]
  近似凸と制約付きサンプルベースフェデレーション最適化について検討した。 各問題に対して,逐次凸近似手法を用いたプライバシー保護アルゴリズムを提案する。 提案アルゴリズムは, 速度, 通信コスト, モデル仕様の点で, 数値的な利点がある。
  論文  参考訳（メタデータ） (2021-03-17T08:38:03Z)
• Constraint-Handling Techniques for Particle Swarm Optimization Algorithms [0.0]
  人口ベースの手法は、従来の方法よりもはるかに複雑な問題を含む、さまざまな問題に対処することができる。 本研究の目的は,アルゴリズムに汎用的な設定を組み込んだPSOに適したCHTを開発し,比較することである。
  論文  参考訳（メタデータ） (2021-01-25T01:49:10Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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