論文の概要: Exploiting Symmetries in MUS Computation (Extended version)

• arxiv url: http://arxiv.org/abs/2412.13606v1
• Date: Wed, 18 Dec 2024 08:34:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-19 13:24:35.340970
• Title: Exploiting Symmetries in MUS Computation (Extended version)
• Title（参考訳）: MUS計算における爆発対称性(拡張版)
• Authors: Ignace Bleukx, Hélène Verhaeghe, Bart Bogaerts, Tias Guns,
• Abstract要約: eXplainable Constraint Solving (XCS) では、満足できない制約の集合から最小不満足な部分集合(MUS)を抽出することが一般的である。 MUSの発見は、高度に対称的な問題に対して計算コストがかかる。 本稿では、既存の対称性処理技術からインスピレーションを得て、よく知られたMUS計算手法を適用して仕様の対称性を利用する。
• 参考スコア（独自算出の注目度）: 11.266189935383476
• License:
• Abstract: In eXplainable Constraint Solving (XCS), it is common to extract a Minimal Unsatisfiable Subset (MUS) from a set of unsatisfiable constraints. This helps explain to a user why a constraint specification does not admit a solution. Finding MUSes can be computationally expensive for highly symmetric problems, as many combinations of constraints need to be considered. In the traditional context of solving satisfaction problems, symmetry has been well studied, and effective ways to detect and exploit symmetries during the search exist. However, in the setting of finding MUSes of unsatisfiable constraint programs, symmetries are understudied. In this paper, we take inspiration from existing symmetry-handling techniques and adapt well-known MUS-computation methods to exploit symmetries in the specification, speeding-up overall computation time. Our results display a significant reduction of runtime for our adapted algorithms compared to the baseline on symmetric problems.
• Abstract（参考訳）: eXplainable Constraint Solving (XCS) では、満足できない制約の集合から最小不満足な部分集合(MUS)を抽出することが一般的である。 これは、制約仕様が解決策を認めない理由をユーザーに説明するのに役立つ。 MUSの発見は、多くの制約の組み合わせを考慮する必要があるため、高度に対称的な問題に対して計算的にコストがかかる可能性がある。 従来の満足度問題の文脈では、対称性がよく研究され、探索中に対称性を検出して活用する方法が存在している。 しかし、満足できない制約プログラムのMUSを見つける際には、対称性が検討される。 本稿では、既存の対称性処理技術からインスピレーションを得て、よく知られたMUS計算手法を適用して、仕様の対称性を活用し、全体の計算時間を高速化する。 その結果,対称問題に対するベースラインと比較して,適応アルゴリズムのランタイムの大幅な削減が示された。

関連論文リスト

• Computing Game Symmetries and Equilibria That Respect Them [77.72705755558839]
  ゲームにおける対称性の同定と利用の計算について検討する。 ゲーム対称性とグラフ自己同型の間には強い関係がある。 与えられた対称性の集合を尊重するナッシュ均衡を求めることは、ブラウワーの不動点や勾配降下問題と全く同じほど難しいことを示す。
  論文  参考訳（メタデータ） (2025-01-15T16:15:16Z)
• Metaheuristics for the Template Design Problem: Encoding, Symmetry and Hybridisation [0.0]
  テンプレート設計問題(TDP)は、多くの対称性を持つ難しい問題であり、それをより複雑にしている。 本稿では,テンプレート設計の適合性を評価することを目的として,多種多様なメタヒューリスティクスを探索し,解析する。
  論文  参考訳（メタデータ） (2024-11-05T06:29:12Z)
• Structured Regularization for Constrained Optimization on the SPD Manifold [1.1126342180866644]
  対称ゲージ関数に基づく構造化正規化器のクラスを導入し、より高速な非制約手法でSPD多様体上の制約付き最適化を解けるようにする。 構造正規化器は望ましい構造(特に凸性や凸の差)を保存または誘導するために選択できることを示す。
  論文  参考訳（メタデータ） (2024-10-12T22:11:22Z)
• Symmetry-Informed Governing Equation Discovery [29.16110821783827]
  本稿では,自動方程式探索における対称性を活用して,方程式探索空間を圧縮し,学習方程式の精度と簡易性を向上させることを提案する。 提案手法は,ノイズに対するロバスト性の向上を実証し,対称性のないベースラインよりも極めて高い確率で支配方程式を復元する。
  論文  参考訳（メタデータ） (2024-05-27T01:58:23Z)
• Learning Layer-wise Equivariances Automatically using Gradients [66.81218780702125]
  畳み込みは等価対称性をニューラルネットワークにエンコードし、より優れた一般化性能をもたらす。 対称性は、ネットワークが表現できる機能、事前に指定する必要、適応できない機能に対して、固定されたハード制約を提供する。 私たちのゴールは、勾配を使ってデータから自動的に学習できるフレキシブル対称性の制約を可能にすることです。
  論文  参考訳（メタデータ） (2023-10-09T20:22:43Z)
• Tapping into Permutation Symmetry for Improved Detection of k-Symmetric Extensions [3.501108734684888]
  本研究では,順応的に置換対称性を利用する手法を提案する。 k)-対称拡張を検出するためのSDP問題を微調整することにより、探索空間の次元を著しく減少させる。 これはアルゴリズムの強化をもたらし、qudit ( k )-対称拡張シナリオにおける (O(d2k) ) から (O(kd2) ) への複雑性を減少させる。
  論文  参考訳（メタデータ） (2023-09-08T06:05:56Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Classical symmetries and QAOA [3.2880869992413246]
  本稿では,量子近似最適化アルゴリズム(QAOA)と最適化対象関数の基本的な対称性との関係について検討する。 本稿では,QAOA力学の量子対称性特性と目的関数の古典対称性群との関係を定式化する。
  論文  参考訳（メタデータ） (2020-12-08T20:02:09Z)

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

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